Օգտագործելով ռեկուրսիա՝ գտիր այն բառերը, որոնք պալինդրոմ են

Պալինդրոմներն այն բառերն են, որոնք ուղիղ և թարս կարդալիս նույն բառն ենք ստանում։ Օրինակ՝ rotor-ը պալինդրոմ է, իսկ motor-ը՝ ոչ։

Ինչպե՞ս կարող ես ռեկուրսիա օգտագործելով հասկանալ՝ բառը պալինդրոմ է, թե ոչ։ Արի սկզբում հասկանանք՝ որն է այստեղ առաջնային դեպքը։ Հաշվենք, որ a բառը պալինդրոմ է։ Իրականում կարիք չկա, որ պարտադիր հաշվի առնենք այն բառերը, որոնք բառարաններում գոյություն ունեն։ Պալինդրոմ կարող ենք հասկանալ ինչ-որ տառերի կույտ, որոնք հակառակ կարդալիս էլ ստանում ենք նույնը, օրինակ՝ xyzyzyx։ Տառերի հաջորդականությունը կոչում ենք տողային։ Հետևաբար, կարող ենք ասել, որ մի տառ ունեցող յուրաքանչյուր տողային պալինդրոմ է։ Տողայինը կարող է պարունակել ոչ մի տառ․ ոչ մի տառ ունեցող տողայինը կոչում ենք դատարկ տողային։ Դատարկ տողայինը նույնպես պալինդրոմ է, քանի որ դիմացից և հետևից այն նույն դատարկ տողայինն է։ Հետևաբար, կարող ենք ասել, որ ամենաշատը մեկ տառ ունեցող տողայինը պալինդրոմ է։ Դա կլինի մեր առաջնային դեպքը․ զրո կամ մեկ տառ ունեցող տողայինը պալինդրոմ է։

Իսկ ի՞նչ կլինի, եթե տողայինն ունենա երկու կամ ավելի տառ։ Այստեղ արդեն մենք ունենում ենք մեր ռեկուրենտ դեպքը։ Վերցնենք rotor պալինդրոմը։ Դրա առաջին և վերջին տառերը նույնն են, հետևաբար այն դեռ համապատասխանում է պալինդրոմի սկզբունքներին։ Իսկ եթե առաջին և վերջին տառերը նույնը չեն, ինչպես motor-ում, ապա տողայինը պալինդրոմ չէ։ Հետևաբար, մենք կարող ենք ասել, որ բառը պալինդրոմ չէ, երբ դրա առաջին և վերջին տառերը տարբեր են։ Քանի որ արդեն ունենք պատասխանը, այս իրավիճակում կարող ենք մտածել մեկ այլ առաջնային դեպքի մասին։ Երբ առաջին և վերջին տառերն ենք ստուգում, ի՞նչ է այն մեզ ասում։ Տողայինը հնարավոր է, որ պալինդրոմ լինի։ Եվ հնարավոր է, որ պալինդրոմ չլինի։ rater տողայինում առաջին և վերջին տառերը նույնն են, բայց տողայինը պալինդրոմ չէ։ Հաշվենք, թե ազատվեցինք առաջին և վերջին տառերից՝ թողնելով ate-ը։ Եվ այս դեպքում առաջին և վերջին տառերը տարբեր են, հետևաբար կարող ենք ասել, որ rater-ը պալինդրոմ չէ։

Ահա թե ինչպես կարող ենք ռեկուրսիայով գտնել՝ արդյոք բառը պալինդրոմ է, թե ոչ։ Եթե առաջին և վերջին տառերը տարբեր են, ապա տողայինը պալինդրոմ չէ։ Եթե նույնն են, ազատվիր առաջին և վերջին տառերից, և պարզիր՝ մնացած տողայինը՝ ենթախնդիրը, պալինդրոմ է, թե ոչ։ Փոքր տողայինի պատասխանը կլինի մեծ տողայինի պատասխանը։ Երբ ռեկուրսիայով հասնում ես մեկ տառ կամ ոչ մի տառ ունեցող տողայինի, ապա բառը պալինդրոմ է։ Ահա մեր քննարկած բառերը․

Ինչպե՞ս այն կբացատրենք կեղծ կոդում։

Նյութը ստեղծվել է Դարթմութի համակարգչային գիտությունների դասախոսներ Թոմաս Քորմենի և Դեվին Բալկքոմի, ինչպես նաև «Քան» ակադեմիայի ծրագրավորման թիմի կողմից։ Նյութը լիցենզավորվել է CC-BY-NC-SA-ի կողմից։