Программалау және программа, программалау тілдері. Программалау тілдерінің түрлері. Программаны түзету (отладка), тестілеу

Шарты соңынан тексерілетін do … while циклінің оператордың жалпы жазылу түрі:

… … …

Цикл тұлғасы ретінде қарапайым немесе құрама оператор қолданылуы мүмкін. Жақшадағы өрнек цикл тұлғасынан кейін тексеріледі. Сондықтан do while цикл тұлғасы ең болмағанда бір рет орындалады. Цикл тұлғасынан кейін жазылған өрнек ақиқат болса (немесе жалған жағдайда ол 0-ге тең болмаса), цикл тұлғасы қайтадан орындалады. Ал өрнек жалған болса (немесе 0-ге тең болса), цикл аяқталады.

#include

 int main()

{inti;

intsum = 0;

for (i = 1; i<= 1000; i++)

{ sum = sum + i; } cout<< "Сумма чисел от 1 до 1000 = " <

7. Функция. Оның программада қолдану ерекшеліктері. Функцияны сипаттау және анықтау. Прототип. Рекурсия. Рекурсия механизмі. Рекурсивтік функция. Оны қолданудың артықшылығы.

Функцияны сипаттау (Описание функции; function declaration) — міндетгі анықтайтын жоғары деңгейдегі программалау тілінің конструкциясы. Функцияға атау беруге (егер қажет болса), оның формальдық параметрлерін көрсетуге және алгоритмнің жүзеге асырылатын міндетін анықтауға қызмет етеді. Функцияны сипаттау программадағы сипаттамалар бөлімінде (мысалы, Паскальда) немесе программалық модуль түрінде әзірленген бас программадан (мысалы, Фортранда) кейін орналасады. Функцияны сипаттау формасы нақтылы тілдің синтаксисімен тағайындалады. Әдетте, Функциялық сипаттау денесі мен функцияның бас тақырыбынан тұрады. Тақырыпта функцияның атауы көрсетіледі және формальдық параметрлері көрсетілуі мүмкін. Ал міндеттің денесінде орындалатын алгоритм міндеттері программаланады.

Рекурсивті алгоритм қаншалықты тиімді? Оның тиімділігін есептей аламыз ба, егер тікелей есептеу алгоритмі квадратты, кіру мәліметтерінің бөліктеуі логарифмді, барлық шешімдердің бірігуі сызықты (кіру мәліметтерінің мөлшеріне байланысты), ал әрқайсысының мөлшері бастапқының төрттен біріне тең болатын барлық кіру мәліметтері 8 бөлікке бөлінетінін білетін болсақ? Бұл есепті шеші оңай емес, оған қалай кірісу керек екендігі де түсініксіз. Дегенмен, «бөл де басқар» түріндегі алгоритмдерді талдау оңай екені анықталды, егер сіздің алгоритміңіздің қадамдары жоғарыда келтірілген жалпы түрдегі алгоритмнің қадамдарына сәйкес қойылса: тура есептеу, кіруді бөлу, бірнеше рекурсивті шақырулар саны және алынған шешімдердің біріктірілуі. Егер осы қадамдар бір-бірімен қалайша біріктірілетінін және әр қадамның күрделілігін білетін болсақ, онда «бөл де басқар» түріндегі алгоритм күрделілігін анықтау үшін келесі формуланы қолдануға болады:

мұндағы DAC —DivideAndConquer алгоритмінің күрделілігі,

DIR — Direct Solution алгоритмінің күрделілігі,

DIV — Divide Input алгоритмінің күрделілігі,

COM — CombineSolutions алгоритмінің күрделілігі.

Осы жалпы формула арқылы алдындағы абзац басында қойылған сұрақ өте қарапайым болып қалады. Тек әр бөліктің белгілі күрделіліктерін формулаға қойсақ болғаны. Нәтижесінде:

немесе кіші жиындар шамасы бірдей болғандықтан, одан да оңай формула:

Мұндай түрдегі теңдіктер рекурренті деп аталады, өйткені функция мәні өз терминдері арқылы беріледі. Сол функцияның басқа шақыруларынан тәуелсіз, тек N-нан тәуелді болатын күрделілік үшін өрнекті тапқымыз келеді.

Факториал мысалына қайтып оралсақ. Факториалды есептеу алгоритмінің барлық кезеңдерін жалпы DivideAndConquer алгоритмімен сәйкес қоялық. Енді осы сәйкестікті пайдаланып, жоғарыда келтірілген жалпы формулаға қою керек мәндерді анықтаймыз. Factorial функциясындағы тура есептеулер ешқандай әрекеттерді қажет етпейді, кіру мәліметтерін бөлу және нәтижелерді біріктіру алгоритмінің әрқайсысы тек бір әрекетті қажет етеді, ал рекурсивті шақыру бастапқы мөлшерден 1-ге кем болатын тек бір есепті шығарады. Нәтижесінде Factorial функциясын есептеу санына келесі рекурентті қатынасты аламыз: