Я прохожу элементарный курс по структурам данных и алгоритмам, книга, которую мы используем, является основополагающей работой CLRS. У меня есть некоторые проблемы с пониманием инварианта цикла, как описано в главе 2.1: Сортировка вставками. В...

Мне нужно придумать инвариант цикла для данного фрагмента кода: //pre: x & y >= 0 //post: z = x^y //computes pow(x, y), x^y int pow(int x, int y){ int z = 1; while(y > 0){ if(y%2==0){ y /= 2; x =...

У меня есть цикл while (показан ниже), который постоянно читает из файла, пока не будет достигнут EOF. Я должен написать инвариант цикла для любого нетривиального цикла. Это тривиальная петля? Если нет, то что будет инвариантом цикла для этого...

У меня есть следующий код для изменения цифр в целом числе: public class integerReversal { public static int reverseNum(int number){ int reversed = 0; int remainder; //{I: ; B: number > 0} while (number >...

Я работаю над тем, как использовать dafny для проверки сортировки вставками с помощью «перестановки» соседних элементов, но я не могу найти разумный инвариант для цикла while, может ли кто-нибудь помочь мне это исправить? Вот ссылка:...

Из следующего кода мне нужно вывести/выбрать инвариант цикла. (|true|) x = 0 ; s = 0 ; while ( x <= n ) { s = s + x ; x = x + 1 ; } (|s = n(n + 1)/2|) Данное решение было s = (x-1)*x/2 ∧ (x ≤ n +1) Я не совсем понимаю,...

Я пытаюсь понять, как инварианты цикла взаимодействуют с разрывами. CLRS 3e (pg19) описывает инвариант цикла как требующий, чтобы Если оно истинно до итерации цикла, оно остается истинным и до следующей итерации. Итак, учитывая следующий...

Я пытаюсь доказать следующий алгоритм RandomSeach-Algorithm и выяснить инвариант для цикла. Поскольку функция randomIndex(..) создает случайное число, я не могу использовать такой инвариант, как ???? ≥ 0 ∧ ???? < ???? − 1 ⇒ ????[????] ≠...