Задача тижня 05.03.12 – 11.03.12

Сюрприз

Хлопці приготували дівчатам подарунки на 8 березня – власноруч зроблені блокноти. Кожний блокнот виготовлявся з N аркушів паперу: стопку аркушів перегинали вдвоє, потім ще вдвоє і так M разів, зшивали, розрізали на окремі сторінки й нумерували їх від першої до останньої. Щоб зробити дівчатам сюрприз, на один із аркушів паперу хлопці нанесли вітальні рисунки з обох сторін.

1. Створіть програму яка визначить суму номерів усіх сторінок блокноту, на яких дівчина може побачити сюрприз, якщо, розгорнувши навмання блокнот, вона потрапила на рисунки на сторінці з номером K.

Вхідні дані

Значення N – ціле число від 1 до 50 (кількість аркушів паперу), вводиться з клавіатури (з файлу або задається як константа);

значення M – ціле число від 1 до 10 (кількість перегину аркушів), вводиться з клавіатури (з файлу або задається як константа);

значення K – ціле число (номер сторінки), вводиться з клавіатури (з файлу або задається як константа).

Вихідні дані (виводяться на екран)

Значення S – сума номерів сторінок з сюрпризами, виводиться на екран.

2. Заповніть тестову таблицю за результатами роботи програми:

Аналіз розв’язку задачі «Сюрприз»

1. Візьмемо стопку з N аркушів, з яких один – кольоровий. Зігнемо ці аркуші вдвоє один раз. Неважко переконатися, що незалежно від того, де був кольоровий аркуш, сума номерів кольорових сторінок дорівнює 8*N + 2.

сума номерів становить K + (K + 1) + (4*N – K) + (4*N – K + 1) = 8*N + 2;

сума номерів становить K + (K – 1) + (4*N – K+ 1) + (4*N – K + 2) = 8*N + 2.

Введемо позначення: S1 = 8*N + 2; D1 = 4*N .

2. При наступному згинанні наш блокнот подвоюється і кольорові сторінки містяться у двох частинах блокноту. Сума номерів сторінок в першій частині залишається такою самою, а в другій частині блокноту номери кожної з чотирьох кольорових сторінок зміщуються на 4*N. Отже, сума номерів усіх кольорових сторінок становить:

S2 = 2*S1 + 4*4*N = 2*S1 + 4*D1 = 2*S1 + D2,

де, D2 = 4* D1.

3. При згинанні ще раз до суми, одержаної на попередньому етапі, слід додати таку ж, де кожний з восьми номерів сторінок потрібно збільшити на 8*N, тобто маємо:

S3 = 2*S2 + 8*8*N = 2*S2 + 4*D2 = 2*S2 + D3,

де D3 = 4*D2.

4. Отже, на кожному наступному кроці згинання шукане значення S_j знаходиться як сума двох складників: подвоєного попереднього результату S_j-1 і вчетверо збільшеного попереднього доданку D_j.

Цілком зрозуміло, що обчислення за такою рекурсивною формулою слід здійснювати в циклі.

Зауважимо, що можна одержати інші подання формули для обчислення суми сторінок.

1. Виразимо формулу через кількість сторінок у блокноті на поточному кроці. Позначимо цю кількість через Р. Тоді:

Р1 = 4*N, S1 = 2*(Р1 + 1);

Р2 = 2* Р1, S2 = 2*2*(Р1 + 1) + 4* Р1 = 4*(Р2 + 1);

Р3 = 2* Р2, S3 = 2*4*(Р2 + 1) + 4* 4*Р1 = 2*4*(Р2 + 1) + 4* 2*Р2 = 8*(Р3 + 1) і т.д.

Отже, на j-тому кроці маємо S_j = 2^j (Р_j + 1).

2. Виразимо формулу через кількість N аркушів, з яких виготовляється блокнот. З попередньої формули, враховуючи, що Р_j = 2^j+1 N, випливає:

S_j = 2^j (2^j+1 N + 1).

Останній варіант дає найпростіший спосіб обчислення шуканої суми номерів сторінок: достатньо знайти значення x = 2^j і тоді

S_j = x (2*N*x + 1).

Таблиця за результатами роботи програми:

Журі оцінило надіслані розв’язки наступним чином: