Дві сторони змінюються. Умова відбирає ті пари, які підходять.
Перебираємо, перевіряємо, виводимо
Іноді відповідь простіше знайти, перевіривши всі можливі значення. Такий спосіб називають перебором.
Визначаємо, які значення можуть мати невідомі.
За допомогою циклів утворюємо можливі пари або трійки.
Умовою if перевіряємо кожен набір.
Виводимо лише ті набори, які підходять.
Якщо перебираємо дві величини, зручно використати два вкладені цикли. Коли одну величину можна обчислити через інші, окремий цикл для неї не потрібний.
Приклад 1. Сторони прямокутника
Дано натуральне число n. Знайдіть усі прямокутники з площею n, сторони яких є натуральними числами. Пари, які відрізняються лише порядком сторін, виведіть один раз.
Перша сторона i й друга сторона j можуть набувати значень від 1 до n. Потрібна пара має задовольняти умову i * j == n.
Якщо обидва цикли почати з 1, отримаємо й 2 × 6, і 6 × 2. Тому починаємо внутрішній цикл із j = i. Так завжди i ≤ j, і кожна пара з’являється один раз. Квадрати також враховуємо.
#include <iostream>
using namespace std;
int main() {
long long n;
cin >> n;
for (long long i = 1; i <= n; i++) {
for (long long j = i; j <= n; j++) {
if (i * j == n) {
cout << i << " " << j << "\n";
}
}
}
return 0;
}
Для n = 12:
1 12
2 6
3 4
Тип long long зберігає більші цілі числа, ніж int. Використовуємо його, щоб добуток сторін не переповнив int. Для навчальних запусків використовуйте n від 1 до 1000: подвійний перебір великих значень працюватиме повільно.
Кожна пара проходить перевірку
Задайте площу від 1 до 30. На одному кроці перевіряємо одну пару i та j. Після завершення внутрішнього циклу збільшуємо i, а j знову починаємо з i.
Знайдені сторони:
Приклад 2. Сто тварин за сто гривень
У старовинній задачі бик коштує 10 грн, корова 5 грн, теля 0,5 грн. Потрібно купити рівно 100 тварин за 100 грн. Ціни умовні. Кількість тварин кожного виду може дорівнювати нулю.
Позначимо кількість биків b, корів k, телят t. Маємо дві умови:
b + k + t == 100: разом 100 тварин.
20 * b + 10 * k + t == 200: вартість 100 грн. Усі ціни й загальну суму помножили на 2, щоб працювати з цілими числами.
Биків може бути від 0 до 10, корів від 0 до 20. Кількість телят не перебираємо, а обчислюємо: t = 100 - b - k. У цих межах t завжди невід’ємне, адже b + k ≤ 30.
#include <iostream>
using namespace std;
int main() {
for (int b = 0; b <= 10; b++) {
for (int k = 0; k <= 20; k++) {
int t = 100 - b - k;
if (20 * b + 10 * k + t == 200) {
cout << b << " " << k << " " << t << "\n";
}
}
}
return 0;
}
Результат: кількість биків, корів і телят
1 9 90
Перевірка: 1 + 9 + 90 = 100 тварин; 10 + 45 + 45 = 100 грн. Перебираємо 11 · 21 = 231 пару. Умову про кількість тварин удруге перевіряти не потрібно: вона вже виконується завдяки формулі для t.
Приклад 3. Числовий ребус
Додатковий приклад. У рівності КНИГА × 3 = НАУКА замініть літери цифрами. Однакові літери означають однакові цифри, різні літери означають різні. Перша цифра кожного числа не може бути нулем.
Тут шість різних літер. Для кожної використовуємо свій цикл. Це довший приклад того самого перебору, його можна розглянути після двох попередніх.
Змінні k, n, i, g, a, u відповідають літерам К, Н, И, Г, А, У.
k та n перебираємо від 1 до 9, решту цифр від 0 до 9.
Перевіряємо, що цифри різних літер не збігаються.
Складаємо два числа й перевіряємо множення на 3.
У НАУКА літера А повторюється двічі. Тому цифри всередині цього числа не мають бути всі різними: важливо, щоб різним літерам відповідали різні цифри.
Відкрити повну програму
#include <iostream>
using namespace std;
int main() {
bool found = false;
for (int k = 1; k <= 9; k++)
for (int n = 1; n <= 9; n++)
for (int i = 0; i <= 9; i++)
for (int g = 0; g <= 9; g++)
for (int a = 0; a <= 9; a++)
for (int u = 0; u <= 9; u++) {
if (k != n && k != i && k != g && k != a && k != u &&
n != i && n != g && n != a && n != u &&
i != g && i != a && i != u &&
g != a && g != u && a != u) {
int first = k * 10000 + n * 1000 + i * 100 + g * 10 + a;
int second = n * 10000 + a * 1000 + u * 100 + k * 10 + a;
if (first * 3 == second) {
cout << first << " * 3 = " << second << "\n";
found = true;
}
}
}
if (!found) {
cout << "Розв’язків немає\n";
}
return 0;
}
Результат перевіреного перебору:
28375 * 3 = 85125
У записі 28375 × 3 = 85125 маємо К = 2, Н = 8, И = 3, Г = 7, А = 5, У = 1. Змінна found спочатку має значення false і стає true, коли знайдено розв’язок. Якщо вона так і залишилася false, виводимо повідомлення.
Варіанти для самостійної роботи
У кожному варіанті два пункти. У числових ребусах початкова цифра багатозначного числа не може бути нулем, а дільник не може дорівнювати нулю. Написи ребусів збережено за оригіналом: це умовні позначення цифр.
У варіанті 14 вважайте, що гирі кладуть лише на протилежну від предмета шальку: кожну гирю або беруть один раз, або не беруть. У варіанті 15 заборона цифр 1 і 2 для літер є окремою умовою цього пункту.
Знайдіть розміри всіх паралелепіпедів, об’єм яких дорівнює числу V, та довжини сторін є натуральні числа. Розв’язки, які утворюються переставленням значень ребер виводити один раз. Наприклад, V=6, тоді розв’язким задачі будуть такі набори чисел: (1, 1, 6), (1, 2, 3)
У рівності АВ+ВС+СА=АВС замініть літери цифрами так, щоб рівність була правильна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть правильну рівність на екран.
Дано натуральне число n. Чи можна представити його у вигляді суми квадратів двох натуральних чисел? Якщо ні, то вивести повідомлення про це. Якщо можна, то вивести значення на екран, причому розв’язки які утворюються переставленням чисел виводити один раз.
У рівності ЛО*С=ОСЬ замініть літери цифрами так, щоб рівність була правильна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть правильні рівності на екран.
У касі в необмеженій кількості є купюри по 3 та 5 грн. Скількома способами можна видати деяку суму S? Вивести всі варіанти та підрахувати їх кількість.
У рівності КОКА + КОЛА = ВОДА замініть літери цифрами так, щоб рівність була правильна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть правильну рівність на екран.
Знайти всі натуральні розв’язки рівняння x2+y2=k2, де x, y та k знаходяться в інтервалі від 1 до 30. Розв’язки які утворюються переставленням чисел x та y виводити один раз
У рівності ТРИ + ТРИ + ТРИ = ДЫРА, причому (Ы + Ы) : Ы = Ы замініть літери цифрами так, щоб рівність була правильна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть правильну рівність на екран.
У тарганів та павуків разом 74 лапки. Скільки може бути тарганів та павуків, якщо у таргана – 6 лапок, а у павука 8 (вивести всі можливі варіанти).
У рівності ТРИ * ТРИ = ШЕСТЬ замініть літери цифрами так, щоб рівність була правильна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть правильні рівності на екран.
Приписати до числа 1022 зліва та справа по одній цифрі так, щоб отримане шестизначне число було кратне 7, 8 та 9. Вивести отримане число на екран.
У рівності ТЭТА + БЭТА = ГАММА замініть літери цифрами так, щоб рівність була правильна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть правильну рівність на екран.
У тарганів та павуків разом 50 лапок. Скільки може бути тарганів та павуків, якщо у таргана – 6 лапок, а у павука 8 (вивести всі можливі варіанти).
У рівності БУКВА • 6 = СЛОВО замініть літери цифрами так, щоб рівність була правильна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть правильну рівність на екран.
Приписати до числа 102 зліва та справа по одній цифрі так, щоб отримане п’ятизначне число було кратне 4, 5 та 6. Вивести отримане число на екран.
У рівності УДАР + УДАР = ДРАКА замініть літери цифрами так, щоб рівність була правильна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть правильну рівність на екран.
Вартість відправлення посилки N грн. В наявності є марки за вартістю 1, 5, 10 гривень. Чи можна цими марками оплатити відправлення посилки за умови, що кількість марок не перевищує 5 штук (вивести всі можливі варіанти та їх кількість). Якщо не можна, то вивести повідомлення про це.
У рівності МОСЬКА : И = ШАВКА замініть літери цифрами так, щоб рівність була правильна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть правильну рівність на екран.
Знайдіть двозначне число, перша цифра якого дорівнює різниці між цим числом і числом, записаним тими ж цифрами, але в зворотному порядку.
У рівності Г+О=Л-О=В*О=Л-О=М-К=А замініть літери цифрами так, щоб рівності були правильні. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть правильні рівності на екран.
У тризначному числі закреслили першу зліва цифру; отримане двозначне число помножили на 7. В результаті вийшло вхідне тризначне число. Яке?
У рівності СТО+ СОТ= ТОС замініть літери цифрами так, щоб рівність була правильна. СТО, СОТ і ТОС – тризначні числа (наприклад, СТО=С*100+Т*10+О). Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть правильну рівність на екран.
В касі є монети по 2, 5 та 10 коп. Чи можна цими монетами видати суму Sum (вивести всі можливі варіанти та їх кількість)? Якщо не можна, то вивести повідомлення про це.
Скільки булок було у пекаря? Відповіддю служить найменше можливе число «много» в ребусі БУЛОК + БЫЛО = МНОГО
Коли тризначне число, дві перші цифри якого однакові, а третя дорівнює 5, розділили на однозначне число, то в залишку отримали 8. Знайти ділиме, дільник і частку.
У рівності ab*ck=bbb замініть літери цифрами так, щоб рівність була правильна. Тут ab та ck двозначні числа, а bbb трьохзначне число(ab=a*10+b, bbb=b*100+b*10+b). Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть всі варіанти правильних рівностей на екран.
Є по одній гирі вагою по 100, 200, 300, 500, 1000, 1200, 1400, 1500, 2000 і 3000 г. Чи можна цими гирями зважити предмет вагою в n грамів? (вивести всі можливі варіанти та їх кількість)? Якщо не можна, то вивести повідомлення про це.
У рівності ПОДАЙ − ВОДЫ = ПАША замініть літери цифрами так, щоб рівність була правильна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть правильну рівність на екран.
У рівності a1+2b=cd замініть літери цифрами так, щоб рівність була правильна. Тут a1, 2b та cd двозначні числа(a1=a*10+1, 2b=2*10+b, cd=c*10+d). Однаковим літерам повинні відповідати однакові цифри, різним – різні (ясно, що a, b, c, d !=1 та !=2 ). Виведіть всі варіанти правильних рівностей на екран та підрахуйте їх кількість.
У рівності СО=РОКА замініть літери цифрами так, щоб рівність була правильна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть правильну рівність на екран.
У рівності abcd+befd=edfbg замініть літери цифрами так, щоб рівність була правильна. Тут abcd, befd чотиризначні числа, а edfbg п’ятизначне число (наприклад, abcd=a*1000+b*100+c*10+d, а
edfbg=e*10000+d*1000+f*100+b*10+g). Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть всі можливі варіанти правильних рівностей на екран.
У рівності БУК=АШКА замініть літери цифрами так, щоб рівність була правильна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть правильну рівність на екран.
Надрукуйте щасливі номери трамвайних білетів, які дорівнюють квадрату будь-якого натурального числа. Шестизначний номер білету називається щасливим, якщо сума перших трьох цифр дорівнює сумі останніх трьох цифр. Вивести на екран номер білету та число, квадратом якого він є, по 5 пар у рядку. Наприклад:
108900 330 122500 350 128164 358 137641 371 155236 394
173056 416 185761 431 203401 451 206116 454 216225 465
...
У рівності МАМ=ОНТЫ замініть літери цифрами так, щоб рівність була правильна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть правильну рівність на екран.