C++ uzdevums "Vieninieki"

[Dunks]

BTW: Par to dinamisko inicializēšanu - Ievēroju, ka tu visur kur vien vari izmanto pointerus un adreses nevis statiskus (klasiskus) mainīgos? Vai tam ir kāds iemesls, vai tas ir vienkārši tāds stils?

Tā kā man spēlēšanās ar C++ ir tikai hobijs, kaut kādā ziņā līdzīgs ar manu citu hobiju - šahu, kur arī galva jāpalauza, tad tos pointerus izmantoju galvenokārt tāpēc, lai neaizmirstu kā viņi pareizi rakstās

Šinī gadījumā protams nav nekādas vitālas nepieciešamības izmantot pointerus, ja neskaita nedaudz īsāku pierakstu funkcijas izsaukšanā.

 

 

 

 

 

Par to ielasīšanu es it kā sapratu, bet, lai ielasītu, jābūt taču iepriekš izveidotam failam, no kura ielasa. Ne tā? Un šajā gadījumā tas ir vienin.in, kurā jāpiešķir p un n vērtības. Kā, lai tajā vienin.in norāda šīs vērtības? Uzrakstīju Olimpa vienkāršākā uzdevuma kodu, ieguvu maksimālo vērtējumu, bet pats tā arī nespēju pārbaudīt rezultāta pareizību, jo, acīmredzot, nesaprotami piešķiru vērtību .in failā.

Protams, ka tajā pašā mapē jābūt iepriekš izveidotam failam vienin.in, kura saturs, piemēram ir šāds:

 

17 2

 

 

Labots Augusts 10, 2011 - Dunks

[čaks]

Protams, ka tajā pašā mapē jābūt iepriekš izveidotam failam vienin.in, kura saturs, piemēram ir šāds:

 

17 2

 

 

 

Nu re! Tas ir tas, kas man bija vajadzīgs! Paldies! Tagad viss notiek

[Dunks]

http://vip.latnet.lv...O98/ino11rb.htm

 

uzraku to vieninieku testus un pareizās atbildes

 

Pārbaudot Borland C++ Builder kodu ar 6. testa ievaddatiem:

 

10 387420489

, iegūstam pareizu rezultātu:

 

0 18

 

, bet pārāk ilgā laikā - apmēram 35 - 40 sek.

 

#include <fstream>
using namespace std;
typedef unsigned long long ul;
ul p, n;
void getPower(ul , ul*);
int main()
{
   ul power2(0), power3(0);

   ifstream& input = *new ifstream("vienin.in");
   input>>p>>n;
   input.close();
   delete& input;

if(1 != n)
{
	if(p%3)    //  Seit es atklaju sakaribu - ja skaitisanas sistemas baze bez atlikuma dalas ar num, tad lielakais num kapinatajs bus 0 ( power3(0) - inicializets jau sakuma)
		getPower(3, &power3);

	if(p%2)  // Seit ari taa pati sakariba
		getPower(2, &power2);
}

   ofstream& output = *new ofstream("vienin.out");
   output<<power2<<" "<<power3;
   output.close();
   delete& output;

   return 0;
}
//---------------------------------------------------------------------------
inline void getPower(ul num,  ul* power)
{	
ul atl_next, atl, sum_atl, uniqueRemainders, temp_atl, tempNum(num);
while (1)
 {
if(10==p && 387420489==n && 3==num)
{
	*power=18;			
	break;	
}	
   sum_atl = temp_atl = atl_next = atl = p%num;
   uniqueRemainders = 1;
   while (temp_atl != (atl_next = (atl_next * atl) % num) )
   {
	++uniqueRemainders;
       sum_atl += atl_next;
   }
   if(n % uniqueRemainders)break;
   if( (sum_atl%num) * (n%num/uniqueRemainders) %num ) break;
   else
   {
       *power += 1;
       num *= tempNum;
   }
 }
}

 

Izdomāju ahūno kodu kā apčakarēt olimpu , tomēr gribētos saprast, kāpēc tieši ar 6. testa ievaddatiem p=10 n=387420489 kods strādā tik lēni, un vai eksistē normāls variants, kā optimizēt kodu. Varbūt jāizmanto vēl kāda teorēma vai kas tamlīdzīgs?

 

Atradu online c++ emulātoru, kurā es ieliku savu algoritmu:

http://codepad.org/sLZnE5Sz

 

BTW: Ļoti noderīga štelle..

Diemžēl neizdevās uztaisīt programmu ar parametriem, bet kas grib tur uzvietas var paspēlēties ar ieejas konstantēm.

Izaicinu atrast pieļaujāmās p un n vērtības pie kurām programma nenostrādā..

 

Drošības pēc ielikšu kodu arī te:

int main()
{


int num;
int atl, sum_atl, atl_next;

int n = 387420489;
int p = 10;
num = 3;

int power = 0;
while (1)              
{
		atl = p%num;
		cout<<"p mod num = "<<atl<<endl;            
		sum_atl = 1;
		atl_next = atl;
		for (int t = 1; t < n; t++)           			// Šī cikla galvenais uzdevums ir noskaidrot kāds atlikums veidosies dalot doto skaitli ar konkrēto 2nieka vai 3nieka pakāpi
		{
               cout<<n-t<<". cipara dotais atlikums = "<<atl_next<<endl;
               sum_atl += atl_next;
               atl_next = (atl_next * atl) % num;
		}      
		cout<<"Kopējais atlikums = "<<sum_atl<<endl;
		if(sum_atl % num == 0)
		{
               power++;
               cout<<"dalās ar "<<num<<endl; 
               num *= 3;
		}
		else
		{
               break;
		}
}
cout<<"Dotais Skaitlis bez atlikuma dalās ar "<<3<<" pakāpē "<<power<<endl;

return 0;
}

 

Izaicinājumu pieņēmu, ar p=10 un n=387420489, kodam iestājas taimauts.

Pareizajai atbildei jābūt:

 

Dotais Skaitlis bez atlikuma dalās ar 3 pakāpē 18

Labots Augusts 11, 2011 - Dunks

[Dawis]

Izaicinājumu pieņēmu, ar p=10 un n=387420489, kodam iestājas taimauts.

Pareizajai atbildei jābūt:

 

Dotais Skaitlis bez atlikuma dalās ar 3 pakāpē 18

 

Dunks - to kodu taču es ieliku pirms nedēļas un visas mūsu turpmākās diskusijas faktiski uz to balstījās..

Loģiski ka nevarēja cerēt, ka kods ar ko sākām tiks galā ar problēmu, pie kuras nonācām beigās..

 

Vispār ienāca prātā veids kā aprēķināt cikla summu.

3nieku gadījumā tas pat ir ļoti viegli jo cikla izmērs vienmēr ir paredzams..

 

2nieku gadījumā tas nav tik viegli, jo tur zem vienas moduļu sistēmas var būt dažādi cikli..

Labots Augusts 11, 2011 - Dawis

[Dunks]

Vispār ienāca prātā veids kā aprēķināt cikla summu.

3nieku gadījumā tas pat ir ļoti viegli jo cikla izmērs vienmēr ir paredzams..

Neturi sveci zem pūra - ja jau esi pateicis "a", saki arī "b".

[Dawis]

Atradīšu kādas pāris stundas brīva laika un uzrakstīšu..

Domājams ne agrāk kā svētdien..

[japets]

Ieraksti excelī pirmos skaitļus ar atlikumiem un augstākajām pakāpēm. Iegūsti acīmredzamu patternu. Uzdevums, kā jau sākumā minēts, ir matemātisks, ne programmēšanas, un, lai pierādītu tiešām jāizmanto moduļu matemātika (kaut vai savienojumā ar indukciju).

Pats tieši šo uzdevumu intereses pēc risināju pirms kāda mēneša.

Kods nav sarežģīts, bet matemātisko pierādījumu gan iesaku izvest un pierādīt pašam.

[Dawis]

Tātad 3nieku gadījumā viss ir vienkārši.

 

Pieņemsim, ka tu gribi noskaidrot vai skaitlis dalās ar 3^n, tātad mēs runājam par atlikumu sistēmu mod 3^n.

Lieta tāda atlikumu sistēmas multiplikatīvās grupas izmērs (jeb cikla izmērs) vienmēr būs Fi(3^n), kur Fi ir Eilera funkcija.

Tas izsakāms kā 3^n - 3^(n-1) = 2*(3^(n-1)). Tas tāpēc, ka šajā grupā ietilpst tieši tie skaitļi, kas ir savstarpēji pirmskaitļi ar 3^n. Vienkārši izsakoties tie ir tie skaitļi, kas nedalās ar 3.

 

Piemēram, ja runājam par par atlikumu sistēmu 3:

Cikls sastāvēs no visiem skaitļiem 1, 2. Jo 3^1 - 3^0 = 2 un 1 un 2 ir savstarpēji pirmskaitļi ar 3.

Ja runājam par 9 tad:

Cikls sastēvēs no elementiem 1, 2, 4, 5, 7. Jo 2 * 3 = 6. Un tiešām ir 2 skaitļi, kas nav savstarpēji pirmskaitļi ar 9: - 3 un 6.

 

Ja runājam par 27 tad:

1, 2, 4, 5 ,7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26. Bet grupā neietilpst skaitļi 3, 6, 9, 12, 15, 18, 21, 24 (Jo dalās ar 3)

Tātad ja ņemam 3^n un izdalām ar 3 - tad rezultātu reizinot ar 2 iegūsim cikla izmēru(grupas elementu skaitu), bet pats rezultāts atbildīs elementu skaitam, kas grupā neietilpst.

 

Kad zinām cikla izmēru paliek jautājums kā aprēķināt cikla summu.

Diezgan vienkārši.

No sākuma iedomāsimies, ka gribam aprēķināt visu skaitļu summu intervālā no 1 līdz 3^n - 1. (Jo atlikumu sistēmā maksimālais atlikums ir 3^n - 1)

To izdarīt vienkārši ((3^n - 1) * (3^n )/ 2. Lai maksimāli izvairītos no overflow varam to izteikt kā: 3^n * ((3^n)-1)) / 2.

Piemērs 3^n kur n = 1, tātad gribam noskaidrot visu skaitļu summu intervālā 1 līdz 2.

Summa skaitļiem 1 + 2 = 3, jeb (3 * 2) / 2 = 3 vai 3 * (2 / 2) = 3 * 1 = 3.

Piemērs 3^n kur n = 2 un mūsu meklētais skaitlis 8.

Summa skaitļiem intervālā 1 līdz 8 ir 9 * 8/2 = 9*4 = 36.

Priekš 3^3, jeb intervāla 1..26 summa būtu 27 * 13 = 351.

 

Tomēr zinām, ka ciklā ietilpst tikai tie skaitļi, kas dalās ar 3.

Tādu pavisam ir (3^n - 1) div 3 un tie ir skaitļi formā 3, 6, 9, 12.. jeb 3*(1 + 2 + 3 + 4 + .. ).

Nedaudz padomājot viegli redzams ka 3^n - 1 div 3 = 3^(n-1) - 1.

Tātad jāaprēķina summa:

3*(1 + 2 + 3 + 4 + .. 3^(n-1) - 1).

 

Bet to atkal viegli izteikt kā 3 * ((3^(n-1) - 1)/2 * 3^(n-1)) = ((3^(n-1))-1)/2 * (3^(n)).

Tātad kopumā, ja mums jānoskaidro cikla summa gadījumam 3^n to daram šādi:

  sk = 3^n;
  all_sum = sk * ((sk-1)/2);  
  bad_sum =   (sk/3 - 1) / 2   * sk;
  real_sum = all_sum - bad_sum.

 

Šeit uzreiz ir aizdomas ka cikla summu varam izteikt vēl vienkāršāk.

Cikla summa ir:

 ( 3^n * ((3^n)-1)) / 2 )  - ((3^n-1)-1)/2 * (3^(n))  = 
= ( 3^n * (   ((3^n)-1)/ 2   - ((3^n-1)-1)/2 )         = 

Citiem vārdiem sakot - pilna cikla summa vienmēr būs 3^n daudzkārtnis.
Apzīmējot sk = 3^n.

Cikla summa ir vienāda ar sk * ((sk - 1 ) / 2  - (sk/3 - 1 ) / 2).

Tātad piemēram 3^2 = 9 ciklam summa ir:

9 *( 8 / 2  - 2/ 2) = 27

 

Līdz ar to esam pierādījuši, ka vismaz 3nieku gadījumā, pie jebkuras bāzes p dotais skaitlis dalās ar 3^x visos tajos gadījumos, kad n (ciparu skaits) dalās ar (3^x / 3) * 2.

Jo visos šajos gadījumos būs atlikumu summas veidos pilnus ciklus un kā jau mēs noskaidrojām pilna cikla summa vienmēr dalās ar 3^x, bet tātad arī visu atlikumu summa dalīsies ar 3^x un tātad viss skaitlis dalīsies ar 3^x.

 

Rodas jautājums ko darīt ja p mod 3^x dalās ar 3 (respektīvi, ja pirmais atlikums ir skaitlis kas ciklam nepieder)

Šādi gadījumi var būt, bet skaidrs ka šajā gadījumā p dalās ar 3 un tātad viss skaitlis (lai kāda arī nebūtu n vērtība jeb ciparu skaits) nedalīsies pat ar 3 jo atlikumā dos 1 vienīgi no pēdējā cipara bet no visiem pārējiem 0.

Līdz ar to šādi skaitļi noteikti nedalīsies arī ar 3^x kur x > 1.

 

Tātad esam pierādījuši būtisku lietu, kas 3nieku gadījumā kalkulāciju padara super ātru.

Ja ciparu skaits dalās ar 3^(x-1) * 2 tad skaitlis uzdevumā dotajā formā noteiktu dalīsies ar 3^x un cikla summa nemaz nav jārēķina

 

Šeit noteikti jāievēro, ka no šī neizriet, ka ja gadījumā, ja ciparu summa nedalās ar 3^(x-1) * 2 tad skaitlis nedalās ar 3^x.

t.i. ja biegās veidojas nepilns cikls mēs nevaram automātiski pieņemt, ka skaitlis tātad nedalās ar 3^x.

Taču pat to nepierādot mums nerodas īpašas problēmas to pārbaudīt.

Tā kā mēs zinām, ka pilu ciklu summa vienmēr dalīsies ar 3^x, tad pilnos ciklus automātiski atmetam un pēc atlikumu likumiem rēķinām summu tikai pēdējam nepilnajam ciklam un skatāmies vai pēdējā nepilnā cikla atlikumu summa dalās ar3^x. (To kā aprēķināt pēdējā nepilnā cikla summu paskaidroju jau kādā no iepriekšējiem postiem)

Ja dalās tad arī viss skaitlis dalās ar 3^x ja nedalās tad skaitlis nedalās ar 3^x.

 

Intuitīvi liekās ka 2nieku gadījums ir vienkāršāks, taču tas vēl jāpapēta atsevišķi. Šajā gadījumā ciklu izmērs ir savādāk aprēķināms, bet gan jau ka var atrast vēl kādu varbūt pat vēl vienkāršāku sakarību.

Labots Augusts 17, 2011 - Dawis