Програмистите често представляват цикли са склонни да се постигне определена цел: да се намери елемент с желаните свойства, вид и т.н. Но как да се уверите, че целта ще бъде постигната без да се извършват на самия цикъл ..? Това ще ни помогне да се повтаря инвариант.
Loop инвариант - това твърдение, като се позовава на променливите на програмата, което остава вярно в началото и в края на изпълнение на всеки цикъл на итерация.
Да разгледаме използване на линия инвариантна от примера на индекса за търсене на най-малкия елемент в цяло число масив.
Да предположим, че имаме масив. състояща се от азот елементи. Представяме на променливата TemporarySmallest (индекса в момента е най-малкият) и да го настроите, равна на 0, преди започване на теста. След това, ние ще сравните [TemporarySmallest] последователно с [1], а [2]. за [М-1]. Ако установите, че [TemporarySmallest] повече от който и да е от [к]. актуализирайте TemporarySmallest на стойност. Ще означаваме промяна nextToCheck индекса на елемента трябва да бъдат проверени.
Loop инвариант ще изглежда така:
- TemporarySmallest е в [0, nextToCheck),
- за всички к в [0, nextToCheck) извършва А [к]> = A [TemporarySmallest].
[А, б) означава всички числа, които са в интервала от А до В. включително. но без да се включват б.
С други думи, най-малкия елемент на масива с известна индекс TemporarySmallest се изследва в интервала [0, nextToCheck). Тази декларация трябва да е вярно в началото и в края на всяка итерация.
Инициализира променлива в непроменящо се така, че това е вярно преди цикъла:
-- индекс 0. малкия елемент и е единственият елемент в изследваната интервала [0,1). До се запазва неизменна.
На всяка стъпка nextToCheck цикъл се увеличава с 1. и, ако е необходимо, променя TemporarySmallest:
-- така че неизменна линия остава вярно в края на всяка итерация. Следователно, в края на цикъла остане непроменен, - най-малкия елемент на масива с известна индекс TemporarySmallest ще се изследва в интервала [0, nextToCheck).
Състоянието на затваряне цикъл е липсата на елементи масив да бъдат изпитани: nextToCheck == п. По този начин, контур инвариант запазването на ни уверява, че в края на цикъла (изчерпването на елементите да бъдат тествани) се установи, че индексът на най-малкия елемент TemporarySmallest - постигната целта на един цикъл. Тя може да бъде записано като
контур инвариантна Uslovie_okonchaniya_tsikla => Целта на цикъла
Вместо крайни условия, можете да използвате за състоянието на цикъла. В нашия случай това е: nextToCheck контур инвариантна ! (Uslovie_vypolneniya_tsikla) => Целта на цикъла Така, че избрахте непроменящо цикъл и осигурява запазването му, ние можем да гарантираме постигането на целта, без изпълнението на самата линия. Имайте предвид, че използването на контур инвариант може да се разглежда отделно повторение, тъй като всеки един от тях започва с една и съща държава - истина линия инвариант, и в този смисъл, не съдържа "следа" от предишните повторения. В резултат на това аргументът за това дали цикълът се изпълнява правилно, сведена до проверка на това дали контур инвариант истината се възстановява в края на повторение. Проверете знанията си в на подготвителния цикъл: При съставянето на циклите могат да бъдат удобни за концепцията за области на несигурност. изчислителни методи, използвани в математиката. Обхватът на изменение на параметрите на проблема (в този пример: [0, п)) може да бъде разделена на две части: изследвания регион (за които намерено TemporarySmallest [0, nextToCheck)) и региона на несигурност ([nextToCheck, п)) .. Трябва да сте цикъл, така че на всяка итерация на диапазона на несигурност е намален. Нека да се върнем към нашия пример. В началото на първата итерация на изследваната област е единична точка 0 и областта на несигурност е [1, п). Във втория етап на зоната на несигурност намалява до [2, п). - третият .. до [3, н) и т.н., докато най-накрая се обърна към празното множество, които не съдържат точки. Помислете още един пример - Избор Сортиране по низходящ ред. Да предположим, че искате да се справи със масив от п числа. Ние намираме най-малкия елемент и го поставете в края на масива, позицията н-1. След това сред останалите елементи отново да избере най-малката и го поставете в позиция N-2 и така нататък. D. На аз ти итерация подредени елементи ще заемат позиции от първа до N-1. и останалите не са избрани - от 0 до I-1. За най-малката функцията използване елемент FindMin (Int на [], Int п). Връща индекса на най-малкия елемент, и е написана въз основа на горния пример. Представяме на променливата numSorted. посочващ броя на сортираните масив елементи. Loop инвариант е: Непосредствено преди да се инициализира стойността на цикъл numSorted: като контур инвариантна е вярно. На всяка итерация брой numSorted увеличава. За да се постигне това, най-ниската сред първите избран [0, п-numSorted) несортиран елементи и се разменят (използване на функцията за размяна ()) в п-numSorted елемент По този начин, сортирани "опашка" на масива всеки път се удължава с един елемент, и неподреден "глава" се намалява. Цикълът завършва при достигане numSorted == п.
Какво да четат
Свързани статии