Forum Coders' city Strona Główna Coders' city
Nasza pasja to programowanie!
 

 PomocPomoc   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy  RejestracjaRejestracja 
Archiwum starego forum + teoria    RSS & Panel/SideBar
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

Potrzebuję szybkiej odpowiedzi na moje pytanie... Zasady

[C++] Generowanie trójkąta Pascala

Idź do strony 1, 2, 3  Następny

 
Odpowiedz do tematu    Forum Coders' city Strona Główna -> C i C++
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
spy



Dołączył: 01 Maj 2012
Posty: 11

PostWysłany: Wto Maj 01, 2012 11:21 am      Temat postu: [C++] Generowanie trójkąta Pascala Odpowiedz z cytatem Pisownia

Kod:
#include <cstdio>
#include <cstring>

int main()
{  
    char tab[105][105][60];
    const char zero=48, jeden=49;
    
                    tab[0][0][0]=49;
                    tab[1][0][0]=49;
                    tab[1][1][0]=49;
                    tab[2][0][0]=49;
                    tab[2][1][0]=50;
                    tab[2][2][0]=49;
                    tab[3][0][0]=49;
                    tab[3][1][0]=51;
                    tab[3][2][0]=51;
                    tab[3][3][0]=49;
                    

   for(int i =4; i<101; i++)
   {    
                                                  
          
        for(int j=1; j<=((i/2)); j++)        
        {
                    char ZASTE[60];
        
                    for(int z=0; z<strlen(tab[i-1][j-1]); z++)
                    {
                          ZASTE[z] = tab[i-1][j-1][z];  
                            
                    }

                    
                    if(strlen(tab[i-1][j]) > strlen(ZASTE))
                    {
                                                                      
                                     for(int z = strlen(ZASTE); z>0; z--)
                                     {
                                         ZASTE[z] = ZASTE[z-1];  
                                     }
                                    
                                      ZASTE[0]=48;
                                    
                                     if(strlen(tab[i-1][j]) > strlen(ZASTE))
                                     {
                                           for(int z = strlen(ZASTE); z>0; z--)
                                           {
                                             ZASTE[z] = ZASTE[z-1];  
                                           }
                                    
                                           ZASTE[0]=48;
                                                            
                                     }                                      
                    }
                    
                    
                    int x=0;

                    for(int z = strlen(ZASTE)-1; z>=0; z--)
                    {                                                                                
                            tab[i][j][z] = ((tab[i-1][j][z] + ZASTE[z] - 48) + x);
                            
                            x=0;
        
                                  if(z>0)
                                  {                                          
                                    if(tab[i][j][z]>57)
                                    {
                                       tab[i][j][z]-=10;
                                      
                                       x=1;                                                  
                                    }  
                                  }
                                  
                    }
                    
                    if(tab[i][j][0]>57)
                    {
                         tab[i][j][0]-=10;            
                                      
                         for(int z = strlen(tab[i][j]); z>0; z--)
                         {                                
                            tab[i][j][z] = tab[i][j][z-1];  
                         }
                        
                         tab[i][j][0]=jeden;                              
                                      
                    }
                    
                    
                                    
                    int a=strlen(ZASTE);
                    
                    for(int p=0; p<a; p++)
                    {
                         ZASTE[p] = 0;    
                    }
                    
    
                                  
       }
      
       for(int l=1; l<=((i/2)); l++)
       {
                              for(int z =0; z<strlen(tab[i][l]); z++)
                              {
                                tab[i][i-l][z]=tab[i][l][z];  
                              }  
       }  
      
      
                                    
       tab[i][0][0]=49;
       tab[i][i][0]=49;

}

  
       int t;
      
       scanf("%d", &t);
       while(t--)
       {
              int k;
              
              scanf("%d", &k);
              
              for(int i =0; i<=k; i++)
              {                                    
                   printf("%s ", tab[k][i]);        
              }
              printf("\n");  
                        
       }
          

    
    return 0;
}






Program generuje Trójkąt Pascala. Jak można przyspieszyć ten program ?
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
lethern



Dołączył: 09 Paź 2007
Posty: 969

PostWysłany: Wto Maj 01, 2012 12:18 pm      Temat postu: Odpowiedz z cytatem Pisownia

Nie za bardzo umiem rozczytać Twoj algorytm, ale jeśli to on powoduje przekroczenie czasu, to może warto napisać go od nowa - np. próbując zrobić to na 2 wymiarowej tablicy, gdzie masz takie działanie:

Kod:

tab[0][0]= 1   // pierwszy wiersz
tab[1][0]= 1  // drugi wiersz
tab[1][1]= 1

for( 1 <= nr_wiersza < ile_wierszy-1 )
  // nr_wiersza oznacza wiersz, ktory *jest* wypelniony, i dzieki ktoremu wypelnimy nastepny
  ostatni_element = nr_wiersza  

  nowy_wiersz = nr_wiersza+1  
  nowy_ostatni_element = ostatni_element+1

  // w nastepnym wierszu wstaw jedynki na poczatku i koncu
  tab[nowy_wiersz][0] = 1
  tab[nowy_wiersz][nowy_ostatni_element] = 1

  // oblicz następny wiersz, korzystająz z aktualnego
  for( 0 <= j < ostatni_element )
    tab[nowy_wiersz][j+1]= tab[nr_wiersza][j]+ tab[nr_wiersza][j+1]



rezultat
Cytat:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1


BTW, Twój program dla 800 wierszy - jakkolwiek działa - wykonuje się u mnie około 4 sekund, przy czym mój dla 1000 wierszy wykonuje się raczej niezauważalnie, więc mam nadzieję, że Ci to załatwi problem

_________________
używasz Dev-Cpp? tools->editor options -> use tab character (włącz), smart tabs (wyłącz)... albo ściągnij np. Visual Studio C++ free. kpop
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Wyślij email
spy



Dołączył: 01 Maj 2012
Posty: 11

PostWysłany: Wto Maj 01, 2012 9:24 pm      Temat postu: Odpowiedz z cytatem Pisownia

Przykład:
pierwsza linijka to liczba testów.
druga to numer wiersza z trójkąta pascala oczywiście mniejsze niż 101.

wynik to cała linijka z trójkąta.

np.

IN:
1
20

OUT:
1 20 190 1140 4845 15504 38760 77520 125970 167960 184756 167960 125970 77520 38760 15504 4845 1140 190 20 1

I tak mi to działa tylko, że gdzieś mam błąd i nie wiem gdzie. W sensie, błędy wynik. I nie wiem gdzie. Niby wynik są dobre. A i nie mogę zrobić tak jak ty mówisz gdyż wiersz 100 nie pomieści środkowej liczby ma ona 32 cyfry. Dlatego zrobiłem to na charach. Niby działa bezbłędnie ale jednak WA.

PS. SorRy zapomniałem do poprzedniego posta dać wytłumaczenia bardziej zgodnego z tym co oczekuje.

I jeszcze char zawsze ma o 1 wymiar więcej gdyż ten niby dodatkowy przechowuje znaki.
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
lethern



Dołączył: 09 Paź 2007
Posty: 969

PostWysłany: Wto Maj 01, 2012 11:04 pm      Temat postu: Odpowiedz z cytatem Pisownia

Okej, przepraszam, nie zdalem sobie sprawy, że będą tu używane wielkie liczby i trzeba pozbyć się typów podstawowych.
Znalazłem zadanie na spoju, Trójkąt Pascala (TROJPASC)

Oto proponowana metoda, ale jeszcze nie sprawdziłem, czy przechodzi.

Do obliczenia Trójkąta Pascala może przydać się algorytm z symbolem Newtona
http://pl.wikipedia.org/wiki/Symbol_Newtona
Jest tam jego rozwiązanie (optymalniejsza wersja)
Kod:
function WspNewtona( n, k : integer ) : integer;
var
    wynik : integer;
    i : integer;
begin
    wynik := 1;

    for i := 1 to k do
        wynik := wynik * (n - i + 1) div i;

    WspNewtona := wynik;
end;


Brakuje nam do tego jeszcez biblioteki do wielkich liczb - użyłem tej:
https://mattmccutchen.net/bigint/, tylko musiałem przekleić niezbędne pliki w jeden plik, żeby dało się wysłać na spoj. W załączniku jest.




BTW, jakbyś mógł z pierwszego posta z linii 73 i 74 wywalić białe znaki, bo rozszerzają post

BTW2:
Cytat:
6932999 2012-05-02 00:16:23 lethern Trójkąt Pascala zaakceptowano
edit run 0.09



big_integers.cpp
 Opis:
biblioteka do wielkich liczb w 1 pliku

Pobierz
 Nazwa pliku:  big_integers.cpp
 Wielkość pliku:  28.18 KB
 Pobierano:  28 raz(y)


_________________
używasz Dev-Cpp? tools->editor options -> use tab character (włącz), smart tabs (wyłącz)... albo ściągnij np. Visual Studio C++ free. kpop
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Wyślij email
Mgr.Dobrowolski



Dołączył: 18 Cze 2006
Posty: 503

PostWysłany: Sro Maj 02, 2012 5:40 am      Temat postu: Odpowiedz z cytatem Pisownia

liczby mają nie więcej niż 30 cyfr
potrzebne jest tylko dodawanie
całość jakieś 30 linijek
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Wyślij email Numer GG Tlen
spy



Dołączył: 01 Maj 2012
Posty: 11

PostWysłany: Sro Maj 02, 2012 8:42 am      Temat postu: Odpowiedz z cytatem Pisownia

Nie prawda przecież sam wygenerowałem środkową setną liczbę i naprawdę ma ona 32 cyfry.

No dobrze Lethern załóżmy, że skorzystałbym z tego algorytmu ale przecież mój działa bezbłędnie.
Więc czemu dostaje WA?? Jestem dopiero początkujący w c++ siedzę w tym od początku kwietnia. I jeszcze nie za bardzo ogarniam to ale z dnia na dzień jest coraz lepiej. Mówię o początkach programowania więc inny język jak np. java nie za bardzo rozumiem.


Właśnie mi chodziło o to zadanie ze spoja ;].
Nie mogę modyfikować moich postów na które otrzymałem odpowiedź.

A i gdzie mam wstawić ten pilki big_integers.cpp ??

Lethern jeśli byś mógł zrób tak>> http://ideone.com/ wejdź i skompilu swój program i mój i wyniki sprawdź przy pomocy WinMerge porównaj oba wyjścia dla tych samych danych testowych i zobacz gdzie jest różnica i pokaż oba wyjścia THX ;]
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
Mgr.Dobrowolski



Dołączył: 18 Cze 2006
Posty: 503

PostWysłany: Sro Maj 02, 2012 10:53 am      Temat postu: Odpowiedz z cytatem Pisownia

czyli 30 cyfr
sprawdź rachunki oVFLy
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Wyślij email Numer GG Tlen
spy



Dołączył: 01 Maj 2012
Posty: 11

PostWysłany: Sro Maj 02, 2012 12:00 pm      Temat postu: Odpowiedz z cytatem Pisownia

zwracam honor to jest liczba z środkowa setnego wiersza 100891344545564193334812497256 dokładnie ma 30 cyfr ale i tak unsigned long long int tego nie pomieści.
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
Mgr.Dobrowolski



Dołączył: 18 Cze 2006
Posty: 503

PostWysłany: Sro Maj 02, 2012 2:31 pm      Temat postu: Odpowiedz z cytatem Pisownia

lethern tu musimy pokazać całe wiersze, być może nawet wielokrotnie te same - liczenie symbolu Newtona to zły pomysł

liczyłem na intach, każda liczba to 4 cyfry w układzie o podstawie równej miliard (czyli 9 cyfr dziesiętnych)

SPOJ moje 30 linijek samodzielnego kodu w C ocenił 0.00 sekundy (0.01 dla C++)

spy zapomnij na razie o bibliotece do wielkich liczb, dokończ to co zacząłeś
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Wyślij email Numer GG Tlen
lethern



Dołączył: 09 Paź 2007
Posty: 969

PostWysłany: Sro Maj 02, 2012 3:05 pm      Temat postu: Odpowiedz z cytatem Pisownia

spy do tego pliku, który wkleiłem, dodalem 2 rzeczy: obsługę obliczania symbolu Newtona (tak jak pisałem w poście, metodą optymalną z wikipedii) oraz obsługę zadania (kilka linijek, pętla i wyświetlenie wyniku symbolu newtona). Jest to w sumie 40 linijek

Nie wiem czemu WA, jeśli chcesz to wklejam na koncu plik z ostatnim wierszem (100)
Sprawdź jakie masz wyniki dla skrajnych danych... spacje itd., nie mam więcej pomysłów

Mgr.Dobrowolski wiem że nie jest to najlepszy sposób, ale jedyny który wymaga mniej niż godzinę pracy i przechodzi. Pisanie obsługi wielkich liczb od nowa, tylko po to żeby mieć 0.00 zamiast 0.09 nie lezy w moim zadaniu ;p



output.txt
 Opis:

Pobierz
 Nazwa pliku:  output.txt
 Wielkość pliku:  2.25 KB
 Pobierano:  36 raz(y)


_________________
używasz Dev-Cpp? tools->editor options -> use tab character (włącz), smart tabs (wyłącz)... albo ściągnij np. Visual Studio C++ free. kpop
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Wyślij email
Wyświetl posty z ostatnich:   
Odpowiedz do tematu    Forum Coders' city Strona Główna -> C i C++ Wszystkie czasy w strefie CET (Europa)
Idź do strony 1, 2, 3  Następny
Strona 1 z 3

 
Skocz do:  
Możesz pisać nowe tematy
Możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach
Możesz dodawać załączniki na tym forum
Możesz pobierać pliki z tego forum




Debug: strone wygenerowano w 0.04409 sekund, zapytan = 13
contact

| Darmowe programy i porady Jelcyna | VB4all | Tansze zakupy w Helionie | MS Office Blog |