Основи програмування на С ++ для початківців

Задача: Побудова періодичної дробу

Есть (вводиться з терміналу) правильна раціональний дріб a / b (запис у вигляді простий дроби).
– і б – цілі числа;
– якщо дріб правильна, то a < b.

Потрібно програмно визначити період періодичної дробу і вивести її в форматі з десятковою крапкою, виду 0.12(34) (з курсу шкільної арифметики пам'ятаємо, що це 0.12343434… – нескінченна дріб).

Ускладнюємо завдання тим, тому, що система числення записи нескінченної дробу може бути довільною і вибирається випадково (при введенні даних).

Наприклад, в 10-тичної системі ми повинні отримати:
1 / 12 = 0.08(3)
11 / 13 = 0.8(461538)
2 / 5 = 0.4
А в 2-ічной системі, соответственно:
17 / 47 = 0.(01011100100110001000001)

Це 1-я задача. А після вирішення цієї першого завдання, ставимо собі завдання 2: переробити програму так, щоб на кожному кроці (визначення цифри) не робити повний пошук вже зустрічалися раніше залишків…

Рішення:

Насамперед, згадаємо як раціональний дріб (1/3) перетворюється в нескінченну (0.3333… или 0.(3)) – це можна детально почитати тут – Звернення звичайних дробів на десяткові і назад:

    • У циклі знаходимо приватне і залишок від ділення чисельника на знаменник.
    • Приватне – це чергова цифра в нескінченній записи. Зберігаємо залишки на кожному кроці.
    • Множимо залишок на підставу системи числення – це у нас буде чисельник для наступного кроку ітерації.
    • Якщо залишок на якомусь етапі дорівнює нулю, то дріб – кінцева.
    • Інакше шукаємо залишок в числі раніше збережених. якщо знайшли, то ми знайшли період (далі все буде періодично повторюватися).
    • Якщо не знайшли, то зберігаємо поточний залишок і повертаємося до обчислення наступного розряду.

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

Як легко бачити, весь алгоритм починається з рядка 39 і займає всього 12 строк – все інше це введення і підготовка даних:

(Внутрішня механіка відбувається не зовсім очевидна, тому передбачений режим діагностичного висновку – якщо запускати програму з будь-яким параметром)

І тепер ми бачимо, що на кожному кроці нам потрібно Шукати отриманий залишок в масиві (векторі) на збіг з раніше отриманими. це марнотратно. знаючи, як працює алгоритм, можна піти на такий трюк:

    • для знаменника N залишок може мати тільки N значень 0…N-1
    • створимо масив з N елементів, і розмітили його значенням -1, яке означає “таке значення залишку ще не зустрічалося”…
    • а ось якщо на черговому кроці ми отримаємо значення M, то в елемент [M] масиву запишемо номер ітерації, на якому було це значення…
    • тепер, якщо після чергового кроку, ми отримаємо значення K, то нам не потрібно Шукати це значення в усьому масиві, а потрібно тільки перевірити елемент [До] масиву на його позитивність.

І ось що з цього виходить:

2 думки про "Задача: Побудова періодичної дробу

  1. Програма працює неправильно.
    Перша цифра періоду помилково зараховується до предперіоду, а період, обчислений програмою, починається з другої цифри справжнього періоду.

  2. у мене одне питання, автор сайту хоч перевірять код, який йому відправляють? майже в кожних програмах є купа помилок і помилкових обчислень, не зрозумілі для початківців

залишити коментар

Ваша електронна адреса не буде опублікований. Обов'язкові поля позначені * *