Завдання № 39. Перевірити, чи є натуральне число ступенем двійки » Pascal - основи програмування

Основи програмування на мові Pascal

 

Спонсори

Завдання № 39. Перевірити, чи є натуральне число ступенем двійки

Завдання № 39. Перевірити, чи є натуральне число ступенем двійки
Формулювання. Дано натуральне число n. Перевірити, чи представляє воно собою нату-ральную ступінь числа 2.
Рішення. Простіше кажучи, нам потрібно відповісти на питання: чи можна звести число 2 в ка-кую-небудь натуральну ступінь (або в нульову ступінь, так як 20 = 1), щоб вийшло число n?
Взагалі, для вирішення цього завдання існує досить красиве рівність, що виконується для всіх натуральних ступенів числа 2, що дозволяє отримати відповідь за допомогою однієї єдиної логічної побітової операції:

n and (n - 1) = 0

Позначимо його як (1).
Справа в тому, що натуральна ступінь числа 2 з показником p в двійковому вигляді завжди представляється як одиниця з p нулями праворуч. Це відбувається тому, що двійковий запис цього числа в десятковому вигляді представляється як 1 * 2p + 0 * 2p-1 + ... + 0 * 21 + 0 * 20, де все пропускної-щенние доданки мають коефіцієнт 0, і з цього запису легко відновити двоичное перед-уявлення: 10 ... 00, тут нулів всього p. Тому якщо ми віднімемо від будь-якого ступеня двійки 1, то отримаємо число 1 ... 11, де всього p одиниць (точніше кажучи, це буде число 01 ... 11). У результаті, якщо ми застосуємо до цих двох числа побітову кон'юнкцію, то завжди будемо отримувати результуюча-ющее число, рівне 0.
Примітка: побітова кон'юнкція - це бінарна операція, яка еквівалента звичайні-ної кон'юнкції, застосованої до двійковим розрядам операндів (двох вихідних чисел), що стоять на однакових позиціях у двійкових уявленнях цих чисел. При цьому результатом примі-вати побітової кон'юнкції є якесь результуюче число, значення відповідних бітів якого залежить від значень бітів вихідних чисел: у відповідному розряді буде знаходитися 1 тоді і тільки тоді, коли на цих позиціях в обох вихідних числах стояли оди-нічно біти, і 0, інакше.
Приклад: виконаємо порозрядну кон'юнкцію двійкових чисел 0110012 та 1010112 (при цьому випишемо їх так, щоб відповідні виконавчі розряди стояли один під одним):
Перший операнд: 0110012
Другий операнд: 1010112
Результат: 0010012

Біти, кон'юнкція яких дасть 0, виділені червоним кольором, а ті, кон'юнкція яких дасть 1 - синім.
Так як 1-й розряд зліва у першого числа дорівнює 0, а у другого - 1, то у відповідний перший розряд результату йде біт 0. 2-е розряди, відповідно, дорівнюють 1 і 0, і в результат сно-ва йде біт 0 . 3-и розряди у обох чисел рівні 1 (виділені синім кольором), тому в 3-й розряд результату йде 1 і так далі.
До речі, наша формула (1) пропускає число 0 у якості ступеня двійки. Так як компіля-тори мови Pascal (гарантовано називаються Borland Delphi 7 і PascalABC) реалізують числові типи даних у вигляді кільцевих відрізків (тобто, наприклад, в типі byte після числа 255 сле-дует число 0, а перед числом 0 - число 255), то в будь-якому такому типі вираз (0 - 1) має неко-лось ненульове бітове подання (так як нульове бітове представлення має лише чис-ло 0), а побітова кон'юнкція числа 0 і будь-якого іншого числа дає в результаті число 0.
Взагалі, так як нам дане нам n є натуральним числом, число 0 вводитися не буде. Однак покажемо, як відсікти 0 при перевірці числа за формулою (1): можна здійснити про-ревірку введеного числа на рівність нулю, і в разі рівності замінити його на будь-яке дру-гое число, свідомо не є ступенем двійки, щоб умова формули (1) відпрацювало пра-вильно:
if n = 0 then n: = 3;
Взагалі, формула (1) потребує доведення в обидві сторони: ми лише довели, що якщо n є ступенем двійки, тобто n = 2p (де p - будь-яке натуральне число або 0), то вираз n and (n - 1) гарантовано дає результат 0. Покажемо це схематично ще раз:
Перший операнд: 100 ... 00
Другий операнд: 011 ... 11
Результат: 000 ... 00

Однак ми також повинні довести, що ніяке інше число n, окрім як ступінь двійки, не може дати 0 в результаті виконання операції n and (n - 1). Однак ми приймемо це утвер-ганізацій без доказу. У підсумку тіло програмки може виглядати так (для натурального n, яке також може бути нулем):
readln (n);
if n = 0 then n: = 3;
writeln (n and (n - 1) = 0);

Проте ми в якості основного рішення візьмемо більш просту ідею: хай дане число n є ступенем двійки. Отже, його можна представити так: 2p = 1 * 2 * 2 * ... * 2 (тут рівно p двійок). Розділивши цей вираз на 2 певну кількість разів, в результаті ми отримаємо число 1.
Якщо ж число n не є ступенем двійки, то на деякому кроці ми отримаємо залишок при діленні на 2. У зв'язку з цим виникає алгоритм:
1) Вводимо n;
2) У циклі з передумовою n> 1 працюємо з n:
  1. Якщо залишок від ділення n на 2 дорівнює 1 (n mod 2 = 1), то виходимо з циклу;
  2. Ділимо n на 2 (n: = n div 2);
3) Виводимо на екран значення виразу n = 1 (якщо цикл завершився, то ця умова ис-тінно і n - ступінь двійки, а якщо ні - то на якомусь кроці ми отримали залишок при діленні на 2 і вийшли через break);
Навіть якщо ввести n, рівне 0, то програма видасть правильну відповідь, тому що не буде осу-ществляя вхід в цикл (2) і на кроці (3) буде виведено значення виразу 0 = 1, рівне false.

 

Код:


  1. program PowerOfTwo;
  2. var
  3. n: integer;
  4. begin
  5. readln(n);
  6. while n > 1 do begin
  7. if n mod 2 = 1 then break;
  8. n := n div 2
  9. end;
  10. writeln(n = 1)
  11. end.

0039.-PowerOfTwo.rar [569 b] (cкачувань: 9)

скачать dle 10.4фильмы бесплатно Наступна сторінка » Завдання № 40. Вивести на екран твір па... Попередня сторінка » Завдання № 38. Перевірити, чи є натурал...