Ինչպես պատրաստվել Ինֆորմատիկայի միջազգային օլիմպիադային/Առաջին քայլեր
Եկեք հիմա սկսենք մեր երկար բայց հետաքրքիր ճամփորդությունը ալգորիթմների աշխարհում։ Բացի YouTube-ի վիդեոներից և խաղերից, համակարգիչները ունեն շատ այլ կիրառություններ։ Օրինակ, նրանք կարող են կատարել բարդ մաթեմատիկական հաշվարկներ։ Սակայն, առանց մեր ուժերը գնահատելու, եկեք սկսենք համեմատաբար պարզ խնդիրներից։ Այդպիսիներից մեկը հետևյալն է՝
Գրել ծրագիր, որը ստանալով որևէ թիվ՝ ստուգում է, թե արդյոք այդ թիվը պարզ է։
Այլ կերպ ասած, մենք պետք է գրենք մի ծրագիր, որը աշխատացնելուց հետո մենք ստեղնաշարից կմուտքագրենք մի թիվ, իսկ ծրագիրը կպատասխանի «prime» կամ «not prime»։ Ինչպես երևի կռահեցիք, prime (փրայմ) բառը անգլերենում նշանակում է պարզ, երբ խոսքը գնում է պարզ թվերի մասին։ Հիշեցման կարգով, պարզ են համարվում այն թվերը, որոնք ունեն միայն երկու բաժանարար՝ մեկը և հենց իրենք։ Օրինակ, 4-ը և 12-ը պարզ չեն, իսկ 5-ն ու 7-ը պարզ են։ 1 թիվը նույնպես պարզ չէ, քանի որ այն ունի միայն մեկ բաժանարար։ Այս պահին, ձեզ խորհուրդ կտայի գիրքը մի քանի րոպեով փակեք, և մտածեք այս խնդրի վրա։ Եթե կարող եք, ցանկալի կլինի, որ գրեք այս խնդիրը լուծող ծրագիր ձեր նախընտրած ծրագրավորման լեզվով։
Ինչպես դուք հաճախ կնկատեք այս գիրքը կարդալիս, շատ խնդիրներ ունեն բազմաթիվ տարբեր լուծումներ։ Երբեմն միարժեք չէ, թե խնդիրը լուծող որ ալգորիթմն է ավելի լավը, որովհետև խնդրի առաջին լուծումը կարող է աշխատել արագ, բայց պահանջել մեծ ծավալի հիշողություն, իսկ երկրորդը կարող է աշխատել դանդաղ, և օգտագործել շատ քիչ հիշողություն։ Այս պատճառով, հաճախ ինֆորմատիկայի օլիմպիադաների ժամանակ ձեզ տրված կլինեն ծրագրի աշխատելու ժամանակի և օգտագործված հիշողության սահմանափակումներ։ Այս խնդրի դեպքում ևս, մենք կսկսենք մի պարզագույն ալգորիթմից, և քայլ առ քայլ կփորձենք այն լավացնել (ինֆորմատիկայի տերմիններով՝ օպտիմիզացնել)։ Ահա առաջին տարբերակը՝
Ալգորիթմ 1. Մենք ուզում ենք ստուգել թե արդյոք n թիվը պարզ է։ Հերթով դիտարկենք 1-ից մինչև n թվերը, և հաշվենք թե սրանցից քանիսն են n-ի բաժանարարները։ Եթե այդպիսիք երկուսն են, ապա մեր ծրագիրը ուրախությամբ կփաստի, որ n-ը պարզ է։ Հակառակ դեպքում էլ, եթե մենք գտել ենք երկուսից ավել բաժանարար, մեր ծրագիրը կասի, որ n-ը բաղադրյալ է (այսինքն պարզ չէ)։
Ահա այս խնդիրը լուծող ծրագիր C++ ծրագրովորման լեզվով։ Մենք կհամարենք, որ դուք ծանոթ եք C++-ի գոնե տարական գաղափարներին։ Եթե ոչ, կան բազում գրքեր, որոնք ձեզ կօգնեն այդ հարցում, ինչպես օրինակ Դեյտելի և Դեյտելի հեղինակած հայտնի գիրքը (առաջին չորս-հինգ գլուխները ձեզ դեռևս բավական են)։