Задачі з вкладеними циклами

Будь-який складний алгоритм завжди складається з декількох простих алгоритмів. Потрібно навчитись їх бачити та комбінувати.

Приклад 1

Знайти 10 перших простих чисел.

В цій задачі використовуються такі алгоритми:

Пошук декількох чисел (10), що задовольняють деякій умові (в нашій задачі: чи є число простим?);
Визначення, чи є число простим?

Зрозуміло, що другий алгоритм вкладений у першій.

Змінні:

Вхідних даних немає.

Вихідні:

n –шукані числа (цілого типу)

Проміжні:

k – лічильник шуканих чисел (цілого типу)
p – ознака простого числа (логічного типу, p=false не просте число, p=true просте число)
i – дільники та параметр циклу (цілого типу)

Алгоритм

Якщо згадати перший алгоритм, то у ньому:
1. До циклу присвоюються початкові значення числу n та кількості чисел k.
2. В тілі циклу while do:
  1. Збільшується значення числа n;
  2. Число n перевіряється на якусь умову: якщо умова вірна, то число друкується та збільшується лічильник таких чисел k.
3. Перевіряється умова продовження циклу: чи надрукована потрібна кількість таких чисел?
  1. Якщо так, то цикл завершується і кінець програми;
  2. Якщо ні, то перехід на початок тіла циклу.
Зрозуміло, що цей алгоритм буде зовнішнім циклом у нашій програмі і перебір та перевірку чисел потрібно починати з числа 1.
Умова, на яку у цьому циклі перевіряється число n, це – чи є це число простим? Алгоритм, який це визначає буде вкладений в перший.
Згадаємо, що число n називається простим, якщо в нього немає дільників в інтервалі [2, n div 2].
Тепер згадаємо другий алгоритм, який перевіряє, чи просте число n:
1. До циклу присвоюємо початкове значення ознаці p=true. Тобто вважаємо, що число n просте.
2. У циклі for (i=2;i<=n/2;i++) будемо шукати дільники числа n. Для кожного i будемо перевіряти умову n % i==0 и, якщо вона вірна (тобто i є дільником n), то установимо значення ознаки p=false.
3. Коли цикл закінчиться, то перевіримо значення ознаки:
  1. якщо p=true, то дільників немає, число n просте.
  2. якщо p=false, то є дільники, число не просте.
Другий алгоритм вкладений у перший перед перевіркою числа n.

Програма

#include <iostream>
using namespace std;
int main()
{
    int n = 1, k = 0, i;  // n - поточне число, k - лічильник простих чисел, i - лічильник циклу
    bool p;                // Прапорець простоти числа
    
    do
    {
        n++;               // Перехід до наступного числа
        p = true;          // Спочатку вважаємо число простим
        
        // Перевірка чи число просте
        for (i = 2; i <= n / 2; i++)
        {
            if (n % i == 0)  // Якщо знайдено дільник
                p = false;   // Число не є простим
        }
        
        if (p)  // Якщо число просте
        {
            cout << n << " ";  // Виводимо його
            k++;               // Збільшуємо лічильник
        }
        
    } while (k <= 10);  // Повторюємо, доки не знайдемо 10 простих чисел
    
    return 0;
}

Результат роботи програми

Відповідь
2 3 5 7 11 13 17 19 23 29

Приклад 2

Дано натуральне число n. Знайдіть його цифровий корінь (від слова цифра, не плутати з коренем квадратним!)

Визначення

Цифровий корінь числа n це цифра (1, 2, 3,...9), яка обчислюється з цифр числа n за таким алгоритмом:

Знайдемо у числі n суму цифр s,
Перевіримо цю суму s:
1. Якщо вона є цифрою (1, 2, 3,...9), то ця сума є цифровий корінь числа n
2. Якщо вона не є цифрою (>9), то візьмемо замість числа n отриману суму цифр s та повторимо алгоритм з пункту 1.

Результат роботи програми

Ввід	Вивід
3456	9
555	6

Змінні:

Вхідні:

n – натуральне число (цілого типу)

Вихідні:

сk – цифровий корінь числа n (цілого типу)

Проміжні:

c – остання цифра числа n (цілого типу)
s – сума цифр числа n (цілого типу)

Алгоритм

В цій задачі використовуються такі алгоритми:
1. Знаходження суми цифр числа;
2. Заміна числа сумою його цифр, поки ця сума >9.
Зрозуміло, що першій алгоритм вкладений у другий.
Згадаємо алгоритм знаходження суми цифр числа n: обчислюємо останню цифру числа, накопичуємо її до суми і відкидаємо останню цифру від числа. Все це робимо поки не переберемо всі цифри числа (у програмі виділено жирним).
У другому алгоритмі:
1. Після знаходження суми цифр числа, замінимо число сумою його цифр (n=s).
2. Перевіримо цю суму s:
  1. Якщо вона є цифрою (s<=9), то цикл завершується. Виконується перехід на перший оператор після циклу (пункт 5).
  2. Якщо вона не є цифрою (s>9), повторимо алгоритм з пункту 3.
Значення отриманої суми присвоюється змінній ck та виводиться на екран.

Програма 1

#include <iostream>
using namespace std;
int main()
{
    long int n;      // Вхідне число
    int c, s, ck;    // c - поточна цифра, s - сума цифр, ck - контрольна цифра
    cin >> n;       // Отримання числа від користувача
    do
    {
        s = 0;       // Обнулення суми цифр
        do
        {   c = n % 10;  // Отримання останньої цифри
            s = s + c;   // Додавання цифри до суми
            n = n / 10;  // Видалення останньої цифри
        } while (n > 0); // Цикл для обчислення суми цифр числа

        n = s;       // Присвоєння сумі цифр для наступної ітерації
    } while (s > 9); // Повторюємо, доки не отримаємо одну цифру

    ck = s;          // Збереження результату
    cout << ck;     // Виведення контрольної цифри
    return 0;
}

Значно простіше можна знайти цифровий корінь числа, якщо помітити, що він є остачею від ділення цього числа на 9. Причому, якщо остача дорівнює 0, то цифровий корінь такого числа дорівнює 9.

Програма 2

#include <iostream>
using namespace std;

int main()
{
    long int n;   // Вхідне число
    int ck;       // Контрольна цифра (цифровий корінь)
    cin >> n;    // Отримання числа від користувача

    ck = n % 9;   // Обчислення залишку від ділення на 9
    if (ck == 0)  // Якщо число кратне 9
    { 
        ck = 9;   // Цифровий корінь дорівнює 9
    }
    
    cout << ck; // Виведення результату
    return 0;
}

Приклад 3

Знайдіть цифрові корені всіх простих чисел з інтервалу [100, 200]. Надрукувати число та відповідний цифровий корінь.

Результат роботи програми

Відповідь
101 2 103 4 107 8 109 1 113 5 127 1 131 5 137 2 139 4 149 5 151 7 157 4 163 1 167 5 173 2 179 8 181 1 191 2 193 4 197 8 199 1

Змінні:

Вхідних даних немає.

Вихідні:

n – просте число (цілого типу)
сk – цифровий корінь числа n (цілого типу)

Проміжні:

i – дільники числа n та параметр циклу (цілого типу)
p – ознака простого числа (логічного типу, p=true просте, p=false ні)

Алгоритм

В цій задачі використовуються такі алгоритми:
1. Перебір всіх чисел з інтервалу [100, 200].
2. Для кожного з цих чисел визначення, чи є воно простим.
3. Знаходження цифрового кореню кожного простого числа. Цей алгоритм в свою чергу складається з двох алгоритмів (дивись приклад 2).
Зрозуміло, що першій алгоритм це зовнішній цикл for з параметром n. Він перебирає числа в інтервалі [100, 200].
Другий алгоритм це пошук дільників i для кожного числа n. Це теж цикл for з параметром i. Цей цикл вкладений у перший.
Якщо число просте, тобто дільників у числі немає (p=true), то виконується третій алгоритм, обчислення цифрового кореню числа n.

Програма

#include <iostream>
using namespace std;

int main()
{
    long int n, m, i;  // n - поточне число, i - лічильник
    int ck;            // Цифровий корінь
    bool p;            // Прапорець простоти числа

    // Перебір чисел від 100 до 200
    for (n = 100; n <= 200; n++)
    {
        p = true;  // Спочатку вважаємо число простим
        // Перевірка на простоту
        for (i = 2; i <= n / 2; i++)
        {
            if (n % i == 0)  // Якщо знайдено дільник
            {
                p = false;   // Число не просте
            }
        }
        // Якщо число просте
        if (p)
        {
            ck = n % 9;      // Обчислення цифрового кореня
            if (ck == 0)     // Якщо число кратне 9
            {
                ck = 9;      // Цифровий корінь = 9
            }
            cout << n << " " << ck << "\n";  // Вивід числа та його цифрового кореня
        }
    }
    return 0;
}

Варіанти задач

Варіант 1

Ввести з клавіатури n натуральних чисел. Для кожного числа знайдіть його цифровий корінь.
Ввести з клавіатури два натуральних числа А і N. Вивести на екран N простих чисел, більших А.
Вводимо з клавіатури число А та натуральні числа, поки не ввели число 0. Знайти кількість чисел взаємно простих з А.
Варіант 2

Вводимо з клавіатури натуральні числа, поки не ввели число 0. Для кожного введеного числа знайдіть його цифровий корінь.
Ввести з клавіатури три натуральних числа А, В і N. Вивести на екран N чисел, більших А у яких сума цифр дорівнює В.
Ввести з клавіатури n натуральних чисел та число А. Знайти кількість чисел взаємно простих з А.
Варіант 3

Ввести з клавіатури n натуральних чисел та число А. Скільки з цих чисел мають цифровий корінь який дорівнює А?
Ввести з клавіатури три натуральних числа А, В і N. Вивести на екран N чисел, більших А у яких В дільників.
Вводимо з клавіатури число А та натуральні числа, поки не ввели число 0. Чи всі ці числа взаємно прості з А?
Варіант 4

Вводимо з клавіатури число А та натуральні числа, поки не ввели число 0. Скільки з цих чисел мають цифровий корінь який дорівнює А?
Ввести з клавіатури три натуральних числа А, В і N. Вивести на екран N чисел, більших А у яких сума дільників кратна В.
Ввести з клавіатури n натуральних чисел та число А. Чи всі ці числа взаємно прості з А?
Варіант 5

Ввести з клавіатури n натуральних чисел. Скільки з цих чисел закінчуються на свій цифровий корінь?
Ввести з клавіатури три натуральних числа А, В і N. Вивести на екран N чисел, більших А у яких сума цифр дорівнює В.
Ввести з клавіатури три натуральних числа А, В і С. В інтервалі [A; B] знайдіть всі числа взаємно прості з С. Підрахуйте їх кількість.
Варіант 6

Вводимо з клавіатури натуральні числа, поки не ввели число 0. Скільки з цих чисел закінчуються на свій цифровий корінь?
Ввести з клавіатури два натуральних числа А і В. В інтервалі [A; B] для кожного числа знайдіть суму цифр. Вивести число та суму його цифр.
Ввести з клавіатури три натуральних числа А, В і N. Вивести на екран N чисел, більших А які взаємно прості з В.
Варіант 7

Ввести з клавіатури n натуральних чисел. Скільки з цих чисел кратні своєму цифровому кореню?
Вводимо натуральні числа з клавіатури, поки не ввели число 0. Для кожного введеного числа знайдіть суму цифр.
Ввести з клавіатури два натуральних числа А і В. В інтервалі [A; B] знайти всі пари взаємно простих чисел.
Варіант 8

Вводимо з клавіатури натуральні числа, поки не ввели число 0. Скільки з цих чисел кратні своєму цифровому кореню?
Ввести з клавіатури три натуральних числа А, В і С. В інтервалі [A; B] знайдіть числа у яких сума цифр кратна С. Підрахуйте їх кількість.
Ввести з клавіатури натуральне число N. З'ясувати, чи є число N елементом послідовності Фібоначчі.
Варіант 9

Ввести з клавіатури n натуральних чисел. Скільки з цих чисел починаються на свій цифровий корінь?
Ввести з клавіатури три натуральних числа А, В и С. В інтервалі [A; B] знайдіть числа у яких кількість цифр дорівнює С. Підрахуйте їх кількість.
Ввести з клавіатури три натуральних числа N, А і В. З'ясувати, чи є число N елементом геометричної прогресії, в якій перший член дорівнює А, а кожен наступний елемент дорівнює попередньому помноженому на В. Наприклад, для чисел А=7 В=2 N=56 відповідь буде YES, а для чисел А=7 В=2 N=15 відповідь буде NO
Варіант 10

Вводимо з клавіатури натуральні числа, поки не ввели число 0. Скільки з цих чисел починаються на свій цифровий корінь?
Ввести з клавіатури два натуральних числа А і В. В інтервалі [A; B] переверніть кожне число.
Ввести з клавіатури натуральні числа N, А і В. З'ясувати, чи є число N елементом арифметичної прогресії, в якій перший член дорівнює А, а кожен наступний елемент дорівнює попередньому плюсу В. Наприклад, для чисел А=5 В=3 N=17 відповідь буде YES, а для чисел А=5 В=3 N=15 відповідь буде NO.
Варіант 11

Ввести з клавіатури два натуральних числа А і В. В інтервалі [A; B] для кожного числа знайдіть його цифровий корінь.
Вводимо натуральні числа з клавіатури, поки не ввели число 0. Для кожного введеного числа знайдіть кількість його цифр.
Ввести з клавіатури три натуральних числа А, В і N. Вивести на екран N паліндромів, більших А які є простими числами.
Варіант 12

Ввести з клавіатури три натуральних числа А, В і С. В інтервалі [A; B] знайдіть числа у яких цифровий корінь дорівнює С. Підрахуйте їх кількість.
Вводимо натуральні числа з клавіатури, поки не ввели число 0. Переверніть кожне введене число.
Ввести з клавіатури три натуральних числа А, В і N. Вивести на екран N чисел Фібоначчі, більших А що є простими числами.
Варіант 13

Ввести з клавіатури два натуральних числа А і В. В інтервалі [A; B] знайдіть числа які закінчуються на свій цифровий корінь. Підрахуйте їх кількість.
Ввести з клавіатури два натуральних числа А і N. Вивести на екран N чисел паліндромів, більших А.
Ввести з клавіатури n натуральних чисел. Скільки з цих чисел паліндроми, що є простими числами?
Варіант 14

Ввести з клавіатури два натуральних числа А і В. В інтервалі [A; B] знайдіть числа які починаються на свій цифровий корінь. Підрахуйте їх кількість.
Ввести з клавіатури два натуральних числа А і N. Вивести на екран N чисел паліндромів, більших А, які є простими числами.
Ввести з клавіатури три натуральних числа А, В і N. Вивести на екран N чисел, більших А які кратні своєму цифровому кореню.
Варіант 15

Ввести з клавіатури три натуральних числа А, В і N. Вивести на екран N чисел, більших А у яких цифровий корінь дорівнює В.
Ввести з клавіатури два натуральних числа А і В. В інтервалі [A; B] знайти всі паліндроми та їх кількість.
Ввести з клавіатури два натуральних числа А і В. З інтервалу [A; B] вивести на екран тільки прості числа Фібонаачі.
Варіант 16

Ввести з клавіатури два натуральних числа А і N. Вивести на екран N чисел, більших А які закінчуються на свій цифровий корінь.
Ввести з клавіатури два натуральних числа А і В. В інтервалі [A; B] знайти всі паліндроми, які є простими числами та їх кількість.
Ввести з клавіатури два натуральних числа А і В. Для кожного числа з інтервалу [A; B] вивести на екран тільки ті дільники, що є членами послідовності Фібоначчі.
Варіант 17

Ввести з клавіатури два натуральних числа А і N. Вивести на екран N чисел, більших А які починаються на свій цифровий корінь.
Ввести з клавіатури два натуральних числа А і В. Надрукувати з чисел Фібоначчі в інтервалі [A; B], тільки прості числа, а також їх порядкові номери в ряду Фібоначчі.
Обчисліть та надрукувати цифрові корені досконалих (совершенных) чисел, що належать діапазону (1; 10000). Виводити число та його цифровий корінь. Пояснення: натуральне число називається досконалим (совершенным), якщо воно дорівнює сумі своїх дільників, включаючи 1 і виключаючи само число. Наприклад, число 6 досконале (6=1+2+3).

Назад Зміст Вперед