[C] Najdłuższy ciąg niemonotoniczny
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!

[C] Najdłuższy ciąg niemonotoniczny

AutorWiadomość
Temat założony przez niniejszego użytkownika
[C] Najdłuższy ciąg niemonotoniczny
» 2018-01-09 21:02:14
Ten program ma znaleźć najdłuższy ciąg niemonotoniczny (co najmniej 3 elementy), wypisać jego długość, w następnej linijce liczbę znalezionych ciągów o takiej długości a później w kolejnych linijkach indeks pierwszego elementu danego podciągu i wszystkie jego wartości, zero na wejściu kończy pobieranie danych.
Problem polega na tym, że nie zawsze działa on poprawnie, siedzę na tym już dość długo i nie mogę znaleźć błędu.
C/C++
#include <stdio.h>

int main( void )
{
    int tab[ 1000 ], indeksy[ 500 ];
    int i, j, rozm, wieksze, dl, maks_dl, k;
   
    printf( "Podaj liczby:\n" );
    i = 0;
    do
    {
        scanf( "%d", & tab[ i ] );
        i++;
    } while( tab[ i - 1 ] != 0 );
   
    rozm = i - 1;
   
    dl = 1;
    maks_dl = 0;
    if( tab[ 1 ] > tab[ 0 ] )
         wieksze = 1;
    else
         wieksze = 0;
   
    for( i = 0; i < rozm - 1; i++ ) // Znalezienie najdluzszego ciagu
    {
        if( wieksze ) // Szukany na przemian mniejszy lub wiekszy
        {
            if( tab[ i + 1 ] > tab[ i ] )
            {
                dl++;
            }
            else
            {
                if( dl > maks_dl )
                     maks_dl = dl;
               
                dl = 1;
                i--;
            }
            wieksze = 0;
        }
        else
        {
            if( tab[ i + 1 ] < tab[ i ] )
            {
                dl++;
            }
            else
            {
                if( dl < maks_dl )
                     maks_dl = dl;
               
                dl = 1;
                i--;
            }
            wieksze = 1;
        }
    }
    if( dl > maks_dl ) // Jesli ciag nie zostal przerwany
         maks_dl = dl;
   
    if( maks_dl >= 3 )
         printf( "%d", maks_dl );
    else
         printf( "%d", 0 );
   
    dl = 1;
    if( tab[ 1 ] > tab[ 0 ] )
         wieksze = 1;
    else
         wieksze = 0;
   
    j = 0;
    for( i = 0; i < rozm - 1; i++ ) // Znalezienie liczby takich ciagow i ich indeksow
    {
        if( wieksze ) // Szukany na przemian mniejszy lub wiekszy
        {
            if( tab[ i + 1 ] > tab[ i ] )
            {
                dl++;
            }
            else
            {
                if( dl == maks_dl )
                {
                    indeksy[ j ] = i - dl + 1;
                    j++;
                }
                dl = 1;
                i--;
            }
            wieksze = 0;
        }
        else
        {
            if( tab[ i + 1 ] < tab[ i ] )
            {
                dl++;
            }
            else
            {
                if( dl == maks_dl )
                {
                    indeksy[ j ] = i - dl + 1;
                    j++;
                }
                dl = 1;
                i--;
            }
            wieksze = 1;
        }
    }
    if( dl == maks_dl )
    {
        indeksy[ j ] = i - dl + 1;
        j++;
    }
    if( maks_dl >= 3 )
    {
        printf( "\n%d", j );
        for( i = 0; i < j; i++ )
        {
            printf( "\n%d -", indeksy[ i ] );
            for( k = 0; k < maks_dl; k++ )
            {
                printf( " %3d", tab[ k + indeksy[ i ] ] );
            }
        }
    }
    else
         printf( "\n%d", 0 );
   
    return 0;
}
Dla następujących danych działa dobrze:
Podaj liczby:
36 -66 -43 58 86 -10 0
3
2
0 -  36 -66 -43
3 -  58  86 -10

A dla tych już niekoniecznie, ponieważ powinno znaleźć tylko dwa ciągi a nie 6, a więc możliwe, że jest jakiś dłuższy ciąg, ale sprawdzając ręcznie nie znalazłem takowego:
Podaj liczby:
88 -68 55 -82 -22 12 99 26 -10 50 -32 -81 -61 -56 24 84 -61 84 -7 -26 16 64 60 -56 47 29 75 -30 -54 -19 42 30 75 -82 -64 76 21 92 -31 -93 15 20 -14 70 61 -96 -79 84 48 90 26 42 -62 31 48 -65 13 51 -100 78 9 -10 -90 72 28 -91 62 -85 -4 -92 38 85 -22 -86 -67 -12 4 18 -43 -57 64 66 -15 16 -97 69 -88 -47 43 -43 -13 -76 -78 0
5
6
0 -  88 -68  55 -82 -22
14 -  24  84 -61  84  -7
34 - -64  76  21  92 -31
40 -  15  20 -14  70  61
56 -  13  51 -100  78   9
87 - -47  43 -43 -13 -76
Edit:
Chyba wiem co jest źle, gdy dany ciąg się kończy to nie sprawdzam czy następne porównywane elementy mają być mniejsze czy większe, robię to tylko na początku. No i zapomniałem też o sytuacji gdy dwa kolejne elementy są sobie równe, spróbuję jakoś to poprawić, może wystarczy.

Edit 2:
Już działa, wszystko przez to, że jakimś pomyliłem znak większości ze znakiem mniejszości gdy sprawdzałem czy ciąg jest najdłuższy, najciemniej pod latarnią, no i ogarnąłem sytuację, w której dwa elementy obok siebie są równe dodając warunek.

Ostateczny kod:
C/C++
#include <stdio.h>

int main( void )
{
    int tab[ 1000 ], indeksy[ 500 ];
    int i, j, rozm, wieksze, dl, maks_dl, k;
   
    printf( "Podaj liczby:\n" );
    i = 0;
    do
    {
        scanf( " %d", & tab[ i ] );
        i++;
    } while( tab[ i - 1 ] != 0 );
   
    rozm = i - 1;
   
    dl = 1;
    maks_dl = 0;
    if( tab[ 1 ] > tab[ 0 ] )
         wieksze = 1;
    else
         wieksze = 0;
   
    for( i = 0; i < rozm - 1; i++ ) // Znalezienie najdluzszego ciagu
    {
        if( wieksze ) // Szukany na przemian mniejszy lub wiekszy
        {
            wieksze = 0;
            if( tab[ i + 1 ] > tab[ i ] )
            {
                dl++;
            }
            else
            {
                if( dl > maks_dl )
                     maks_dl = dl;
               
                dl = 1;
                if( tab[ i + 1 ] != tab[ i ] )
                     i--;
               
            }
        }
        else
        {
            wieksze = 1;
            if( tab[ i + 1 ] < tab[ i ] )
            {
                dl++;
            }
            else
            {
                if( dl > maks_dl )
                     maks_dl = dl;
               
                dl = 1;
                if( tab[ i + 1 ] != tab[ i ] )
                     i--;
               
            }
           
        }
    }
    if( dl > maks_dl ) // Jesli ciag nie zostal przerwany
         maks_dl = dl;
   
    if( maks_dl >= 3 )
         printf( "%d", maks_dl );
    else
         printf( "%d", 0 );
   
    dl = 1;
    if( tab[ 1 ] > tab[ 0 ] )
         wieksze = 1;
    else
         wieksze = 0;
   
    j = 0;
    for( i = 0; i < rozm - 1; i++ ) // Znalezienie liczby takich ciagow i ich indeksow
    {
        if( wieksze ) // Szukany na przemian mniejszy lub wiekszy
        {
            if( tab[ i + 1 ] > tab[ i ] )
            {
                dl++;
            }
            else
            {
                if( dl == maks_dl )
                {
                    indeksy[ j ] = i - dl + 1;
                    j++;
                }
                dl = 1;
                if( tab[ i + 1 ] != tab[ i ] )
                     i--;
               
            }
            wieksze = 0;
        }
        else
        {
            if( tab[ i + 1 ] < tab[ i ] )
            {
                dl++;
            }
            else
            {
                if( dl == maks_dl )
                {
                    indeksy[ j ] = i - dl + 1;
                    j++;
                }
                dl = 1;
                if( tab[ i + 1 ] != tab[ i ] )
                     i--;
               
            }
            wieksze = 1;
        }
    }
    if( dl == maks_dl )
    {
        indeksy[ j ] = i - dl + 1;
        j++;
    }
    if( maks_dl >= 3 )
    {
        printf( "\n%d", j );
        for( i = 0; i < j; i++ ) // Wyswietlenie indeksow i elementow ciagow
        {
            printf( "\n%d -", indeksy[ i ] );
            for( k = 0; k < maks_dl; k++ )
            {
                printf( " %3d", tab[ k + indeksy[ i ] ] );
            }
        }
    }
    else
         printf( "\n%d", 0 );
   
    return 0;
}
P-168546
« 1 »
 Strona 1 z 1