» Forum » Programowanie » [C, C++] Szukam pomocy

Matura 2012 - Trójkąt Pascala

Ostatnio zmodyfikowano 2012-11-25 19:45

mostrom

Temat założony przez niniejszego użytkownika

» 2012-11-25 19:21:47

Dobry wieczór. Rozwiązuję sobie zadanka maturalne i przyszło na zadanie z trójkąta Pascala. Dla przypomnienia:

Trójkąt Pascala to trójkątna tablica liczb, skonstruowana
w następujący sposób: na dwóch bokach trójkąta znajdują się
liczby 1, kolejne liczby wewnątrz trójkąta obliczane są poprzez
zsumowanie dwóch najbliższych liczb położonych w wierszu
powyżej (rysunek 1a).

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

Polecenie też pozwolę zacytować:

Poniższe polecenia odnoszą się do trójkąta Pascala składającego się z 30 wierszy. Wiersze są numerowane od 1.
a) Podaj największą liczbę spośród liczb wchodzących w skład 10-tego, 20-tego i 30-tego wiersza trójkąta Pascala.

Program wypisuje mi jakieś dziwne liczby, w 10 wierszu większy niż w 20.
Te liczby są dość duże, nawet nie sprawdzałem, czy się zmieszczą w int. Tak czy siak stworzyłem sobie klasę trójkąta, żeby zobaczyć w czym tkwi błąd.

int silnia( int n ) {
if( n == 0 )
return 1;

return silnia( n - 1 ) * n;
}
int dwumian( int n, int i ) { // (n nad i) - symbol newtona
return silnia( n ) /( silnia( n - i ) * silnia( i ) );
}

void tablica_out( int * tbl, int n ) {
for( int i = 0; i < n; i++ ) {
cout << tbl[ i ] << " ";
}
}
class trojkat
{
public:
trojkat( int n ); // n to wysokosc trojkata
~trojkat();

void wyswietl();

int najwieksza_z_wiersza( int n );
private:
int _n; //wysokosc
vector < int * > wiersze; //wektor tablic dynamicznych
};

trojkat::trojkat( int n ) {
_n = n; // przypisanie wysokosci
for( int i = 0; i < _n; i++ ) {
int * tablica = new int[ i + 1 ];
for( int j = 0; j <= i; j++ ) {
tablica[ j ] = dwumian( i, j );
}
wiersze.push_back( tablica );
}
}
trojkat::~trojkat() {
for( int i = 0; i < _n; i++ ) {
delete[]( wiersze[ i ] );
}
}
void trojkat::wyswietl() {
for( int i = 0; i < _n; i++ ) {
tablica_out( wiersze[ i ], i + 1 );
cout << endl;
}
}
int trojkat::najwieksza_z_wiersza( int n ) {
int * wsk = wiersze[ n - 1 ];
sort( wsk, wsk + n );
return wsk[ n ];
}

int main() {
trojkat tr( 30 );
tr.wyswietl();
cout << " \n\n\n10: " << tr.najwieksza_z_wiersza( 10 )
<< " 20: " << tr.najwieksza_z_wiersza( 20 )
<< " 30: " << tr.najwieksza_z_wiersza( 30 );

getchar();

return 0;
}

Wartości w trójkącie pascala obliczałem tak jak mnie matematyczka uczyła - z symbolu newtona. Dla n-tego wiersza: (n nad 0) (n nad 1) (n nad 2) .. (n nad n)
Program wyświetla poprawnie tylko 14 wierszy trójkąta, reszta wygląda zupełnie do kitu i to widać że nie o te wartości chodzi. Program zajmuje tylko 340KB pamięci.
Gdzie jest błąd?

P-69874

Savail

» 2012-11-25 19:28:41

heh, akurat ja też przygotowuję się do matury z infy i mam już rok 2012 przerobiony ^^. Szczerze mówiąc to lepiej jest zrobić te zadanie w arkuszu kalkulacyjnym - excel. W tym przypadku, napisanie programu jest dość skomplikowane i zbyt czasochłonne moim zdaniem. A gdy nauczysz się excela to takie zadanka robi się w miarę szybko i w miarę bez błędów

P-69876

ison

» 2012-11-25 19:30:03

To, że

silnia( n ) /( silnia( n - i ) * silnia( i ) );

mieści się w incie nie oznacza, że

silnia( n )

się zmieści.
Aby tego uniknąć generuj go z definicji, którą sam podałeś na początku.

P-69877

mostrom

Temat założony przez niniejszego użytkownika

» 2012-11-25 19:33:38

Nie zwróciłem uwagi, że komputer może nie mieścić jedynie składnika działania. W takim wypadku myślę nad nowym algorytmem z sumą. Napiszę jak będę miał problem ;] Dziękuję

PS. To algorytmy można realizować w Excelu ? xD Myślałem że to tylko program pomocniczy, a zadania typu ten pascal to normalnie w języku programowania..

P-69878

Savail

» 2012-11-25 19:42:34

Z tego co mi się wydaje to na maturze zawsze jest 1 zadanie do wykonania w języku programowania, 1 zadanie do excela i 1 do baz danych(np. Access).
Co do twojego zadanka to zobacz w modelu odpowiedzi opisy co jest oceniane ;]:
"Zastosowanie odpowiedniego formatowania danych i tabeli
oraz wykonanie obliczeń przy pomocy wbudowanych oraz
zaprojektowanych formuł"

P-69879

ison

» 2012-11-25 19:45:41

Tak najprościej generować

#include <cstdio>
#include <algorithm>

#define MAX 30

int tab[ MAX ][ MAX ];

int main()
{
for( int i = 0; i < MAX; ++i ) {
tab[ i ][ 0 ] = 1;
tab[ i ][ i ] = 1;
for( int j = 1; j < i; ++j ) {
tab[ i ][ j ] = tab[ i - 1 ][ j - 1 ] + tab[ i - 1 ][ j ];
}
}

printf( "%d\n", * std::max_element( tab[ 9 ], tab[ 9 ] + MAX ) );
printf( "%d\n", * std::max_element( tab[ 19 ], tab[ 19 ] + MAX ) );
printf( "%d\n", * std::max_element( tab[ 29 ], tab[ 29 ] + MAX ) );
}

P-69881

« 1 »

Strona 1 z 1

» Forum » Programowanie » [C, C++] Szukam pomocy