Функциялар және рекурсия

9-зертханалық жұмыс. Функциялар және рекурсия

1. Төрт нақты сан берілген: x1x1, y1y1, x2x2, y2y2. (х1, y1) (x1, y1) және (x2, y2) (x2, y2) нүктелерінің арасындағы қашықтықты есептейтін distance (x1, y1, x2, y2) функциясын жазыңыз. Төрт нақты санды қарастырып, осы функцияның нәтижесін шығарыңыз.
2. Кемінде төрт санды бағалайтын, if операторын қамтымайтын, бірақ стандартты min функциясын қолданатын min4 (a, b, c, d) функциясын жазыңыз. Төрт бүтін санды алыңыз.
3. Сізге нақты оң сан және бүтін nn беріледі, anan есептеңіз. Шешімді power (a, n) функция түрінде құрыңыз. Сіз стандартты функцияны немесе дәрежелеу амалын пайдалана алмайсыз.
4. nn және mm екі натурал сандар берілген. nmnm бөлшегін азайтыңыз, яғни pp және qq басқа екі санын шығарыңыз, сонда nm = pqnm = pq, ал pqpq бөлшегі азайтылмайды. Шешімді n және m мәндерін қабылдап, екі саннан кортежді қайтаратын ReduceFraction (n, m) функциясы түрінде құрыңыз.
5. Нақты оң aa сан және теріс емес nn беріледі, anan есептеңіз, циклдар мен стандартты pow функциясын қолданбай, бірақ an = a⋅an - 1an = a⋅an - 1 қайталану қатынасын пайдаланып есептеңдер. Шешімді функция power(a, n) түрінде құрыңыз.
6. Екі теріс емес бүтін санның қосындысын қайтаратын sum(a, b) рекурсивті функцияның қосындысын жазыңыз. Барлық арифметикалық амалдардың ішінде +1 және -1-ге қолдануға ғана рұқсат етілген. Сонымен қатар, циклдарды пайдалануға болмайды.
7. Теріс емес n саны беріліп, nn-ші Фибоначчи санын қайтаратын phib (nn) функциясын жазыңыз. Бұл тапсырмада циклдарды пайдалана алмайсыз - рекурсияны қолданыңыз.
8. nn және kk (0≤k≤n) (0≤k≤n) сандарын ескере отырып, СknСnk есептеңіз. Шешімін табу үшін Ckn = Ck - 1n - 1 + Ckn – 1, Cnk = Cn - 1k - 1 + Cn - 1k қайталану қатынасын қолданыңыз. Шешімді C(n, k) функция түрінде құрыңыз.
9. Сізге 0 санымен аяқталатын сандар тізбегі берілген, циклді қолданбай осы сандардың барлығының қосындысын табыңыз.
10.  Сізге 0 санымен аяқталатын бүтін сандар тізбегі берілген, бұл ретті кері тәртіппен басып шығарыңыз. Бұл мәселені шешкен кезде сіз массивтер мен басқа динамикалық мәліметтер құрылымын қолдана алмайсыз. Рекурсияны қолданыңыз.
11. Дәрежеге шығару, nn көбейтуге қарағанда, әлдеқайда жылдам! Ол үшін келесі қайталану қатынастарын қолдану қажет:

an = (a2) n / 2an = (a2) n / 2 жұп nn үшін,

an = a⋅an - 1an = a⋅an - 1 тақ nn үшін.

Көрсеткіштің жылдам алгоритмін жүзеге асырыңыз. Егер сіз бәрін дұрыс жасасаңыз, онда сіздің алгоритміңіздің күрделілігі O(logn)O(logn) болады.

1.  Екі санның ең үлкен ортақ бөлгішін жылдам есептеу үшін Евклид алгоритмін қолданыңыз. Ол келесі қатынасқа негізделген: ЕҮОБ (a, b) = ЕҮОБ (b, a mod b), ЕҮОБ (a, b) = ЕҮОБ (b, a mod b). gcd (a, b) функциясы ретінде рекурсивті Евклид алгоритмін жүзеге асырыңыз.
2.  Солдан оңға қарай 1-ден N-ге дейін нөмірленген ұяшықтар жолағы берілген. Кескінді квадратқа 1 нөмірімен немесе орналастырылған кесектердің сол жақ бөлігінен кейінгі квадратқа алуға немесе қоюға рұқсат етіледі. Бастапқыда жолақ бос. Фишкаларды барлық ұяшықтарға орналастыруыңыз керек.
3.  Зәулім ғимарат nn қабаттан тұрады. Егер сіз шыны шарды pp номерлі қабаттан түсіріп алсаңыз, доп сынады, онда егер сіз допты p + 1p + 1 қабаттан тастасаңыз, онда ол да сынатыны белгілі. Соңғы қабаттан лақтырған кезде де доптың әрдайым сынатыны белгілі. Сіз доп құлап түскен кезде доп сынатын қабаттың минималды нөмірін анықтағыңыз келеді. Сізде тәжірибе жасауға болатын екі доп бар. Сіз олардың барлығын сындыра аласыз, бірақ нәтижесінде сіз қабат санын анықтағаныңызға сенімді болуыңыз керек. Осы жағдайды біле отырып есепті шешу үшін қанша рет допты лақтыру жеткілікті екенін анықтаңыз.