gonskabalbinka Temat założony przez niniejszego użytkownika |
Zwracanie wzorca w C » 2020-04-19 20:21:13 Witiam piszę program w którym mam zwrócić wzorzec wg poniższego schematu ``` 1 22 333 4444 55555 666666 7777777 88888888 999999999 10101010101010101010 1111111111111111111111 ``` kod zamieszczam poniżej char * pattern( const int n )
{
char * result =( char * ) malloc( sizeof( char ) * n * n * n * n );
char * temp =( char * ) malloc( sizeof( char ) * 5 );
memset( result, '\0',( n * n * n * n ) );
memset( temp, '\0', 5 );
if( n < 1 )
return "";
for( int i = 1; i <= n; i++ )
{
for( int j = 1; j <= i; j++ )
{
sprintf( temp, "%d", i );
strcat( result, temp );
memset( temp, '\0', 5 );
}
strcat( result, "\n" );
}
result[ strlen( result ) - 1 ] = '\0';
return result;
}
Zdaję podstawowe testy ale serwer wyrzuca mi bład przy testach randomowych i nie wiem gdzie jest błąd[/code] |
|
pekfos |
» 2020-04-19 22:19:35 | serwer wyrzuca mi bład przy testach randomowych |
Masz "zwrócić" wzorzec, czy program ma go po prostu wypisać? W automatycznie sprawdzanych zadaniach liczy się tylko standardowe wyjście z programu, a to jak je wygenerujesz nie ma znaczenia. Te zadanie nie wymaga żadnych tablic i sugeruję, żebyś je wywalił. Złożoność pamięciowa n 4 na pewno nie pomaga. |
|
gonskabalbinka Temat założony przez niniejszego użytkownika |
» 2020-04-19 22:39:27 Program ma zwrócić stringa jako rezultat wykonania. Podstawowe testy - przypuszczam -, że dla małych n przechodzę ale w testach randomowych dostaję błędy. Być może problem jest w ilości zaalokowanej pamięci. Dla dużych n program będzie musiał alokować dużo.
W każdym razie trzeba by to może alokować wg wzoru 1+2+3+4+5+6+7+8+9+2*10+2*11+2*13+2*14+...+3*100+3*101+ itd, żeby ograniczyć ilość alokowanej pamięci. W każcym razie kompilowałem to w Visual Stodio i dla n==100 czy nawet 200 daje mi prawidłowe wyniki. Tak że sam już nie wiem gdzie jest ten błąd |
|
pekfos |
» 2020-04-20 17:26:34 | Program ma zwrócić stringa jako rezultat wykonania. |
Program, nie funkcja. Nie potrzeba tu żadnych alokacji pamięci. Wyrzuć alokacje pamięci. Wystarczą dwie pętle i dwa printfy. |
|
gonskabalbinka Temat założony przez niniejszego użytkownika |
» 2020-04-20 21:24:15 Znowu się źle wyraziłem. Funkcja ma zwrócić stringa |
|
pekfos |
» 2020-04-20 22:34:57 W takim razie zacznij od ograniczenia zużycia pamięci. To powinno być coś rzędu n2log n. |
|
gonskabalbinka Temat założony przez niniejszego użytkownika |
» 2020-04-21 21:33:58 Kod poniżej to nie mój kod ale warto to rozważyć int digits = 1 + floor( log( n ) / log( 10 ) );
int min = pow( 10, digits - 1 );
int smaller = n < 10 ? 0:( min - 1;
digits = digits *( n - min + 1 ) *( n + min ) / 2 + smaller;
Próbowałem przetestować program z tym wyliczeniem potrzebnej pamięci, ale on też nie przechodzi testów. To jest zadanie o raczej podstawowym stopniu trudności i nie wiem gdzie jest błąd. |
|
pekfos |
» 2020-04-21 22:01:28 Nie miałem na myśli, żebyś dosłownie użył logarytmu. W takim wypadku powinieneś sprawdzić czy w ogóle daje to poprawne wyniki dla przypadków brzegowych. Logarytm podałem w sensie O(n 2log n), nie dokładny wzór. Dobrze byłoby znać powód odrzucenia rozwiązania - normalnie byłaby informacja typu przekroczenie pamięci, czy czasu obliczeń. W twoim kodzie należy poprawić jedno i drugie. strcat() nie nadaje się do takich zastosowań. Każde wywołanie szuka końca napisu w czasie liniowym względem długości napisu, co wykonujesz O(n 2) razy, więc masz całkowitą złożoność O(n 4log 2 n). Możesz to obejść robiąc result += strlen( result );
tylko musisz zachować w dodatkowej zmiennej adres początku napisu, żeby mieć co potem zwrócić. |
|
| « 1 » |