Բարև սիրելի ծրագրավորող (կամ ապագա ծրագրավորող)։
Այսօր կնայենք հարցազրույցների ժամանակ ամենատարածված խնդիրներից մեկը՝ թվի պարզությունը ստւգելու խնդիրը և այդ խնդրի լուծման եղանակներից մի քանիսը։
Սակայն մինչև առաջ անցնելը 2 կարևոր բան
֊ Խնդիրների լուծումները կլինեն JavaScript լեզվով,
֊ Ես ներկայացնում եմ խնդիրը լուծելու գաղափարները և չեմ բացատրելու, թե որ ֆունկցիան իրենից ինչ է ներկայացնում, սակայն կտեղադրեմ համապատասխան հղումները, որպեսզի դու ինքդ ուսումնասիրես դրանք:
Եթե սիրում ես խնդիրներ լուծել, ուրեմն արդեն լուծել ես այսպիսի խնդիր։ Կամ հարցազրույցի ժամանակ առընչվել ես այսպիսի խնդրի։
Նախ հասկանանք խնդիրը։
Ո՞ր թվերն են համարվում պարզ թվեր։
Պարզ թիվ է կոչվում այն բնական թիվը (բացի 1-ից), որը ունի միայն երկու բաժանարար։ Այսինքն բաժանվում են միայն մեկի և իր վրա ։
Ի՞նչպես կարող ենք ստուգել թվի պարզ լինելը։
Ենթադրենք մեզ տրված թիվը N
թիվն է։
Պարզապես կարող ենք մինչև N
բոլոր թվերը հերթով ստուգել և եթե գտնենք 1֊ից և N
֊ից տարբեր այնպիսի թիվ, որի վրա N
֊ը բաժանելիս ստանում ենք 0 մնացորդ, ուրեմն թիվը պարզ չէ։
Ընդունենք, որ մեր ֆունկցիային փոխանցվող արգումենտը միշտ 1֊ից տարբեր բնական թիվ է լինելու {2,3,4,5,...}:
Մեզ պետք է գտնենլ 1֊ից և N֊ից տարբեր թիվ, հետևաբար կարող ենք ստուգել [2, N-1]
միջակայքի թվերը, ներառյալ։
Կոդը տեղադրված է այս հղման մեջ
Այս եղանակի վրա կարող ենք որոշակի օպտիմիզացիաներ կատարել։
Օրինակ կարող ենք ստուգել մինչև N/2
, որովհետև (N/2, n]
միջակայքում այնպիսի թիվ չկա, որի վրա բաժանելիս կստանանք` ամբողջ թիվ (կստանանք 1ից մեծ և 2ից փոքր թվեր)։ Այսպիով մեր քալերի քանակը 2 անգամ կկրճատվի։
Կոդը տեղադրված է այս հղման մեջ
Սակայն կա մեկ այլ, ավելի օպտիմալ տարբերակ, որը սկզբից կբացատրեմ մաթեմատիկական եղանակով։
Ցանկացած բնական, ոչ պարզ N
թիվ կարող ենք ներկայացնել A * B
տեսքով, որտեղ A, B
֊ն նույնպես բնական թվեր են։
Ունենք M
դրական իրական թիվը, որը N
թվի քառակուսի դրական արմատն է՝ M = |√ N|:
Քանի որ M * M = N
և N = A * B
, ապա M * M = A * B
Նկատենք, որ ստորև նշված 3 պայմաններից մեկը միշտ տեղի ունի։
A > M => B < M
A = M => B = M
A < M => B > M
Բոլոր 3 դեպքերի համար 1 ընդհանուր բան կա՝ (A,B)
-ից փոքրագույնի արժեքը փոքր կամ հավասար է M
֊ից (min(A,B) ≤ M)
:
Հետևաբար նրանցից մեծագույնը մեծ կամ հավասար է M
֊ից (max(A,B) ≤ M)
:
Այսինքն, եթե N
թիվը պարզ չէ, ուրեմն [2,M]
միջակայքում գոյություն ունի գոնե 1 այնպիսի թիվ, որի վրա N
֊ը առանց մնացորդ բաժանվում է։ Հակառակ դեպքում թիվը պարզ է։
Այս ալգորիթմը էլ ավելի քիչ քայլում է կատարվում, քայլերի քանակը հասցնելով √N֊ի։
Կոդը տեղադրված է այս հղման մեջ
Հույս ունեմ, այս նյութը քեզ օգնեց նոր գաղափարներ և նոր գիտելիք ստանալու հարցում։ Իսկ եթե ունես այնպիսի լուծման եղանակ, որը այստեղ նշված չէ, շատ ուրախ կլինեմ, եթե քո տարբերակը ուղարկես ինձ, այդպիսով փորձի փոխանակում կանենք։
Top comments (0)