Ще реша изпита" информатика
- Учител Думбадзе В. А. от училище 162 на Кировски район на Санкт Петербург.
Нашата група VKontakte Мобилни приложения:
Изпълнителят на OddM преобразува числото на екрана. Изпълнителят OddM има два отбора, на които са дадени номера:
2. правя странно
Първата от тези команди увеличава числото x на екрана с 1, втората преобразува числото x в числото 2x+1. Например, втората команда преобразува числото 10 в числото 21. Програмата за изпълнителя на OddM е поредица от команди. Колко програми има, които преобразуват числото 1 в числото 27, а траекторията на изчисленията не съдържа числото 26? Траекторията на програмните изчисления е последователността от резултати от изпълнението на всички команди на програмата. Например, за програма 121, с начален номер 7, траекторията ще се състои от числата 8, 17, 18.
Ние използваме метода на динамично програмиране. Нека получим масив dp, където dp[i] е броят на начините за получаване на числото i с помощта на такива команди.
dp[i]=dp[i-1] - ако i е четен.
dp[i]=dp[i-1] + dp[(i-1)/2] - ако i е нечетно.
Но в същото време, ако i-1 = 26 или (i-1)/2 = 26, тогава не се взема предвид. Можете да видите, че за числото 27 ще има формула dp[27]=dp[26] + dp[13] и тъй като dp[26] не се взема предвид, отговорът е същият като dp[13].
Нека изчислим dp[13] (по-нататък ще бъдат дадени стойностите в dp клетките от 1 до 13): 1 1 2 2 3 3 5 5 7 7 10 10 13.
Изпълнителят на OddM преобразува числото на екрана. Изпълнителят OddM има два отбора, на които са дадени номера:
2. правя странно
Първата от тези команди увеличава числото x на екрана с 1, втората преобразува числото x в числото 2x+1. Например, втората команда преобразува числото 10 в числото 21. Програмата за изпълнителя на OddM е поредица от команди. Колко програми имачислото 1 се преобразува в числото 25, а траекторията на изчисленията не съдържа числото 24? Траекторията на програмните изчисления е последователността от резултати от изпълнението на всички команди на програмата. Например, за програма 121, с начален номер 7, траекторията ще се състои от числата 8, 17, 18.
Ние използваме метода на динамично програмиране. Нека получим масив dp, където dp[i] е броят на начините за получаване на числото i с помощта на такива команди.
dp[i]=dp[i-1] - ако i е четен.
dp[i]=dp[i-1] + dp[(i-1)/2] - ако i е нечетно;
Но в същото време, ако i-1 = 24 или (i-1)/2 = 24, тогава ние не го вземаме предвид. Виждате, че за числото 25 ще има формула
dp[25]=dp[24] + dp[12] и оттогава dp[24] не се разглежда, тогава отговорът е същият като dp[12].
Нека изчислим dp[13] (по-нататък ще бъдат дадени стойностите в dp клетките от 1 до 12): 1 1 2 2 3 3 5 5 7 7 10 10.