4 Програмиране на циклични алгоритми
4.1 Концепцията за цикъл
При съставянето на алгоритми за решаване на практически проблеми често е необходимо определени действия да се извършват многократно, всеки път с нови стойности за количествата, включени в повтарящата се група от действия.
Повтарящите се участъци от изчисленията се наричат цикли. Едно преминаване на цикъл се нарича итерация или повторение. Стойностите, които определят броя на повторенията на цикъла, се наричат параметри на цикъла. Параметрите на цикъла могат да бъдат константи и променливи и сред тях трябва да има поне една променлива, чиято стойност се променя, когато цикълът се изпълнява. Параметрите на целочислен цикъл, които се променят с постоянна стъпка при всяка итерация, се наричат броячи на цикъл. Изчислителните процеси, съдържащи цикли, се наричат циклични.
Циклите се състоят от следните части:
подготовка за изпълнение на цикъла (задаване на първоначални стойности на параметрите на цикъла);
определяне на момента на завършване на цикъла (условия за повторение на цикъла);
тяло на контур, включително:
работната част на цикъла, съдържаща действия, пряко свързани с решаването на проблема, за който е разработен алгоритъмът;
подготовка на данни за следващата стъпка от цикъла (промяна на параметрите на цикъла).
Има цикли с предусловие и цикли с постусловие. В цикли с предварително условие условието за повторение на цикъла се проверява преди да бъде изпълнено тялото на цикъла, така че е възможно цикълът никога да не бъде изпълнен. При цикли с постусловие условието за повторение на цикъла се проверява след изпълнението на тялото на цикъла и подготовката на данните за следващата стъпка от цикъла, така че цикълът винаги се изпълнява поне веднъж. Като цяло, циклите с предусловие и постусловие могат да бъдат графично изобразени, както е показано на Фигура 4.1.
В езика C циклите се програмират с помощта на три различниfor, while, do-while изявления. Възможно е принудително прекратяване на текущата итерация и цикъла като цяло. За това се използват операторите break, continue, return, goto. Не се препоръчва прехвърляне на управление отвън към вътрешността на цикъла.
Използването на командата goto води до объркващ, труден за четене код, наречен от програмистите "спагети". Използването на оператора goto сред програмистите се счита за връх на неуместност. За да се избегне командата goto, се използват сложни условия за повторение на цикъл.
На фиг. 4.1 са представени графични диаграми на циклични алгоритми.
а)Цикъл с предусловиеб)Цикъл с постусловие
Фиг.4.1Графични схеми на цикли а) - с предусловие и б) - с постусловие
4.2 Програмиране на цикъл с предварително определен брой повторения
Операторът за цикълforе оператор за цикъл с параметър и предварително условие. Използва се, ако броят на повторенията на тялото на цикъла, първоначалните стойности на параметрите на цикъла, условието за повторение на цикъла и как се променят параметрите на цикъла са известни предварително. Общ изглед на оператора за цикълfor:
S– прост или съставен оператор на езика C – тяло или работна част на цикъла;
p1е разделен със запетаи списък от оператори, които инициират първоначалните стойности на (обикновено) параметрите на цикъла. Тези оператори се изпълняват веднъж преди изпълнението на работната част на цикъла. Обхватът на променливите, декларирани в тази част от цикъла, е цикълът;
p2– списък с оператори и изрази, които определят условието за повторение на цикъла. Изпълнява се преди всяко изпълнение на тялото на цикъла. В този случай, ако стойността на последния израз от списъкаp2е истина (!=0), тогава тялото на цикъла се изпълнява, а ако е невярно (==0), цикълът излиза към следващия програмен оператор;
p3– списък с оператори и изрази за промяна на параметрите на цикъла (подготвяне на данни за следващата стъпка на цикъла). Изпълнява се след всяко изпълнение на тялото на цикъла.
Пример(изчисляване и показване на квадратите на числата от 1 до 10).
за ( i=1; in за n=1, 2, ..., k (k>1).
Решение. Некаxса необходимите стойности. Нека поставимx=1. Тогава първата степен на двеxе равна наx2, което е равно на21 . Ако поставимx=x*2, тогава втората степен на две еx2, което е равно на22. И така нататък. По този начин степента на две от първия додо-тия може да бъде изчислена чрез изпълнение надопъти рекурсивната връзкаx=x2, като предварително се зададеx=1. Такъв алгоритъм може да бъде реализиран с помощта на цикъл с параметър и с предварително условие. Графичната схема на алгоритъма, програмата на езика C, резултатите от изпълнението на програмата приk=15 са показани на фиг. 2.1. Параметърът на цикълаi(степен на две) приема стойностите1,2, ...,k, следователно е брояч.