C++ 16 Prostych Kawałków

[igomako]

/to pisze aurel, ale zapomniał się przelogować.

Nasz kochany profesor daje oto szanse studentom, którzy zawalili laborki - mają napisać do poniedziałku 16 prostych programów. No i faktycznie są one proste, tylko nie wiedzieć czemu niektóre nie działają tak jak by się chciało...

i tak dla przykładu:

 

#include <cstdlib>#include <iostream>using namespace std;int main(int argc, char *argv[]){	int t, y, n, x, p, i;		cin >> t;	while (t)	{		  cin >> x >> n >> p;		  		   		  if (n=0) x=1; 		  if (n=1) x=x;		  y=x; 		  if (x>1)		  for (i=2; i!=n+1; i++) y=y*x;		  y=y % p;  			  cout << y;		t--;	}	cout << endl;	system("PAUSE");	return EXIT_SUCCESS;}

zadanie polega na wyliczeniu y=(x^n) mod p. czy ktos wie może dlaczego ten tu program wogle nie działa...?

Edytowane 11 Stycznia 2007 przez igomako

[Polar]

Może lepiej by było w ten sposób:

#include <iostream>using namespace std;int main(){	int liczba, potega, mod, wynik=1;	cout << "Liczba, potega, modulo: ";	cin >> liczba >> potega >> mod;	for(int i = 0; i < potega; i++) wynik *= liczba;	wynik = wynik%mod;	cout << "\n(" << liczba << " do " << potega << ") mod " << mod << " = " << wynik;	cin.sync();	cin.get();	return 0;}

Nazywaj zmienne najlepiej calymi wyrazami wtedy będzie od razu wiadomo o co biega.

[igomako]

aurel:

SPOJ nie toleruje żadnych nadprogramowych znaków na wyjściu typu: "wynik to: "...

 

z reszta juz zrobilam ten program ;)

problemem była wielkość zmiennych... int po prostu za mały...

z long intem i dzieleniem bezpośrednio po każdym podniesieniu o potęgę wyżej już przeszło.

 

jeszcze tylko 4 programy :)

Edytowane 11 Stycznia 2007 przez igomako

[PelzaK]

a jeszcze lepiej powoli wyrabiać sobei jakąs konwencję.. najlepiej hungaryjską :) i nazywać zmienne np nLiczba, strNazwa, lpData. Potem w pracy przyszłej wszyscy lepiej będą się rozumieć...

[igomako]

a tu kolejny problem - zadanie ma podnosic liczbe x do potegi y. jednakże pojawia się jeden problem:

 

"Uwaga żadna standardowa zmienna w c, c++ nie zmieści liczby z 3000 zer :D."

 

algorytm podnoszenia do potegi jest na tyle banalny, że daruję sobie cytowanie (dla upartych - wygloda podobnie jak w zadaniu cytowanym wczesniej, tylko bez mod p ;)

no i zaskocze was - SPOJ mojego rozwiazania przyjac nie chce. jakies pomysly?

[Ragnor]

Jeśli mają to być liczby całkowite to obczaj za jakąś biblioteką oferującą BigInty, jeśli nie znajdziesz to sam może prosto taką klasę zaimplementować, choćby jako tablica intów a następnie zdefiniować na niej potrzebne operacje: dodawanie/odejmowanie i mnożenie.

[aurel]

szczerze - nie do końca rozumiem, byłabym bardzo wdzięczna za objaśnienie z przykładem lub link lub chociaż frazę do google'a....

[Ragnor]

Jeśli chodzi o przykład to proszę bardzo:

mamy dwie liczby przypuścimy że 123456789 oraz 987654321 (długość tutaj dowolna) zapisujesz je do tablicy np. intów tak aby każda cyfra była w osobnej komórce czyli tak mamy, niech max rozmiar tablicy będzie 12 wtedy:

0 0 0 1 2 3 4 5 6 7 8 9 -- to jest zapis w pierwszej tablicy, wiodące ewentualne pola są wypełnione przez 0

0 0 0 9 8 7 6 5 4 3 2 1 -- druga tablica

jak widać liczbę wpisujesz tak, żeby tablica była wypełniona od końca a pierwsze komórki ewentualnie były wypełnine przez 0.

Teraz dodanie takich liczb polega na zwykłym pisemnym dodawaniu, zaczynasz je od końca tablic i dodajesz kolejne komórki do siebie, tak aby w wyniku w danej komórce było conajwyżej 9 jak jest więcej przenosisz do przodu.

0 0 0 1 2 3 4 5 6 7 8 9

0 0 0 9 8 7 6 5 4 3 2 1

* * * * * * * * * * * 10

więc przenosisz 1 do następnej i dajesz w tej komórce 0.

0 0 0 1 2 3 4 5 6 7 8 9

0 0 0 9 8 7 6 5 4 3 2 1

* * * * * * * * * *11 0

znowu przenosisz 1

ostatecznie tak to będzie wyglądać:

0 0 0 1 2 3 4 5 6 7 8 9

0 0 0 9 8 7 6 5 4 3 2 1

0 0 1 1 1 1 1 1 1 1 1 0

 

Jak już masz dodawanie za jego pomocą robisz mnożenie (w taki sposób jak mnożenie pisamne wygląda).

Oczywiście przedstawiony tutaj sposób jest dziecinnie prosty a przez to mało wydajny, istnieją inne wydajniejsze algorytmy mnożenia i dodawanie długich liczb, lecz chyba tutaj nie o wydajnośc chodzi ;).

[aurel]

a w międzyczasie:

 

program ma wyświetlać ostatnią niezerową liczbę silni z n. i tak na przyklad dla n=3 ma wyswietlac 6, dla n=5 - 2, n=8 -2 itd...

 

#include <iostream>using namespace std;long long int ostatnia(long long int  x);int main(){     long long int  silnia;   int t, n;	bool ok=false;	   cin >> t;	while (t)	{		  cin >> n;		  silnia=n;		  n--;		  while (n)		  {				silnia=silnia*n;				n--;		  }	   // cout << silnia << "\n";	ostatnia(silnia);	t--;	    	}	 cout << endl; return 0;}long long int ostatnia(long long int x){   //cout << x << "\n";  long long int zach_x, i=1;  int   y=0, t;	zach_x=x;	while (x/i) i=i*10;	 i=i/10; 	while (i) 		  {		   t=x/i;		   x=x-t*i;		   i=i/10;		   }	x=zach_x/10;  //  cout << x << "\n";   if (t) cout << t << "\n"; if (t) return 0; if (!t) ostatnia(x);}

program DZIAŁA!

ale - SPOJ go nie przyjmie gdyż przekroczono limit czasu...

 

nie mogę zrobić na intach ani na long intach, bo są za krótkie (już przy n=13 się wysypują a tymczasem n<=1000...)

[atris]

Bo long int siedzi tylko w 32 bitach i ma zakres od -2.1E+10 do 2.1E+10. Masz jeszcze unsigned long int też na 32bit. ale od 0 do 4.2E+10.

 

Jak chcesz 3000 cyfr to jest coś takiego jak long double, czyli 80bitowa zmiennoprzecinkowa. Zakres od 3.4E-4932 do 1.1E+4932. Z tego co wiem nic bardziej szerokiego nie ma.

[aurel]

juz przy long long int pojawia sie 'przekroczono limit czasu'

jesli wezme jeszcze szerszy typ danych to raczej nie pomoze...

[atris]

Aaaa, to nie doczytałem, że to o limit czasu chodzi. Z czego Ty korzystasz, że takimi błędami sypie :|?

 

Może powinieneś spróbować popracować nad algorytmem. Z tego co widzę próbujesz rozwiązać sprawę iteracyjnie, może lepiej było by rekurencyjnie. Bardziej pamięciożerne ale szybsze.

[Ragnor]

Ten program do wyznaczenia ostatniej niezerowej liczby z silni spokojnie może działać na intach, musisz tyko spostrzec kilka algebraicznych właściwości silni i wyniku, który Cię interesuje :).

[tukamon]

'przekroczono limit czasu'

funkcje cin i cout nie naleza do najszybszych.

pomyslec, ze jeszcze rok temu na eti palono ludzi na stosie za to...

[Polar]

"SPOJ" o_O a cóż to jest? Jaka to uczelnia jeśli można wiedzieć :D

[tukamon]

"SPOJ" o_O a cóż to jest? Jaka to uczelnia jeśli można wiedzieć :D

www.spoj.pl

politechnika gdanska.

pierwszy kontakt z urzadzeniem: wooow, fajna sprawa.

n-ty kontakt z urzadzeniem: jak Boga kocham, wysadze to szatanskie nasienie w kosmos... :D

[aurel]

próbowałam i na printfach i scanfach, ale to naprawdę niewiele daje... i wciąż przekroczony limit czasu. naprawdę myślę, że raczej problem pojawia się przy zmiennych ;)

 

Ragnor -> było by naprawdę fajnie, gdybyś powiedział, jakież to magiczne właściwości muszę spostrzec ;)

ja niestety sama z siebie już niewiele mogę wykrzesać (weźcie pod uwagę, że jednego dnia wysłałam na spoja 12 programów! licząc tylko te przyjęte... więc jestem nieco wyrzęta i odmóżdzona...)

 

//edit - ok, dostrzegłam zależność, jeszcze tylko próbuje to jakoś zbić w algorytm :)

 

//edit2:

 

#include <cstdlib>#include <iostream>using namespace std;int ostatnia(int x);int main(int argc, char *argv[]){ int t, n, i, T[1000], x, p;	cin >> t;		while(t)	{			cin >> n;			T[1]=1; T[2]=2;			if (n==1 || n==2) cout << T[n]<< "\n";			else for (i=3; i<n+1; i++) T[i]=ostatnia(T[i-1]*i); 			cout << T[n]; 			t--;	}	cout << endl;		return 0;}int ostatnia(int x){   //cout << x << "\n";  int  i=1, zach_x;  int   y=0, t;	zach_x=x;	while (x/i) i=i*10;	 i=i/10; 	while (i) 		  {		   t=x/i;		   x=x-t*i;		   i=i/10;		   }	x=zach_x/10;if (t) return t;   else ostatnia(x);  return 0;//if (!t) ostatnia(x);//else return t;}

 

czemu to nie działa...?!! :(

 

 

a teraz uwaga - jesli robie w funkcji ostatnia cout << t; wyswietla prawidlowo. jesli return t i w funkcji glownej cout << ostatnia(x) wyswietla uparcie 42960! (sprawdzane na programie cin >> x, cout << ostatnia(x) dla uproszczenia...

 

 

edit kolejny - pokonalam juz returny i tym podobne przeszkodzy wrzucajac jedna zmienna globalna.

no i okazuje się, że mój genialny algorytm wysypuje się przy n=25 wzwyż.

Edytowane 12 Stycznia 2007 przez aurel