Информатика пәнінен № 3841 тапсырма: Алгоритмдер және программалау (Функция, Рекурсия, жолдармен жұмыс, файлдармен жұмыс, сұрыптау, граф)

Талдау

Бастапқы мәндер: f(0)=0, f(1)=1, f(2)=2. Одан әрі: f(3)=f(2)+f(0)=2, f(4)=f(3)+f(1)=3, f(5)=f(4)+f(2)=5, f(6)=f(5)+f(3)=7, f(7)=f(6)+f(4)=10. Демек, «f(6) мәні 7-ге тең» дұрыс, ал «f(7) мәні 11-ге тең» бұрыс. $n>2$ үшін шақырулар саны K(n)=1+K(n-1)+K(n-3), ал K(0)=K(1)=K(2)=1: K(3)=3, K(4)=5, K(5)=7. Сондықтан f(5) үшін 7 шақыру қажет (дұрыс), ал f(4) үшін 4 емес, 5 шақыру қажет (бұрыс). Ең ұзын ішкі шақырулар тізбегі n-1 арқылы өтеді: f(6), f(5), f(4), f(3), f(2), яғни тереңдік 6 емес, 5. f(6) есептегенде аргументі 2 шақырулар: f(6) функциясы f(5) және f(3) шақырады; f(5) функциясы f(4) және f(2) шақырады; f(4) функциясы f(3) және f(1) шақырады; f(3) шақырулары (f(6) және f(4) ішінен) әрқайсысы бір f(2) шығарады. Барлығы f(2) үш рет шақырылады (f(5) ішінен және екі f(3) ішінен), тұжырым дұрыс. Дұрыстары: «f(6) мәні 7-ге тең», «f(5) есептеу үшін f функциясының бірінші шақыруын қоса алғанда 7 шақыру қажет», «f(6) есептегенде функция аргументі 2 болатындай дәл үш рет шақырылады».