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

Задачі на перебір варіантів

Приклад 1

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

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

ВвідВивід
12 1 12
2 6
3 4

Змінні:

Вхідні:

Вихідні:

Алгоритм та програма

  1. Спочатку вводимо число n, що є площею прямокутника.
  2. Задачу будемо розв’язувати методом перебору. Спочатку з’ясуємо, які значення можуть приймати змінні j, i (простір перебору), що є сторонами прямокутнику. Ясно, що змінні можуть змінюватись від 1 до n. Потім виберемо ти з них, для яких вірна умова i*j=n. Тоді програма буде така:
    ПрограмаРезультат роботи

    Введіть число 12
    1 12
    2 6
    3 4
    4 3
    6 2
    12 1
    
  3. Ця програма перебирає n*n варіантів, це дуже багато. Крім того, з результатів роботи програми видно, що деякі рішення повторюються. Щоб відкинути рішення, що повторюються для сторони j зменшимо простір перебору.
    Замість for (j=1;j<=n;j++) зробимо
    for (j=i;j<=n;j++)
    Тобто, відкинемо ті значення j, що менші і. Тоді програма буде така:
    ПрограмаРезультат роботи

    Введіть число 12
    1 12
    2 6
    3 4
    

Приклад 2

Старовинна задача. Скільки можна купити биків, корів та телят, якщо бик коштує 10 руб, корова 5 руб, теля 0,5 руб та на 100 руб потрібно купити 100 голів скота?

Змінні:

Вихідні:

Алгоритм та програма

  1. Задачу будемо розв’язувати методом перебору. Спочатку з’ясуємо, які значення можуть приймати змінні k,b,t (простір перебору).
  2. Мінімальна кількість биків, яку можна купити це 0. Максимальна кількість биків, яку можна купити на 100 руб буде 10 (бо бик коштує 10 руб). Тобто, простір перебору буде такий: 0<=b<=10.
  3. Мінімальна кількість корів, яку можна купити це 0. Максимальна кількість корів, яку можна купити на 100 руб буде 20 (бо корова коштує 5 руб). Тобто, простір перебору буде такий: 0<=k<=20.
  4. Мінімальна кількість телят, яку можна купити це 0. Максимальна кількість телят, яку можна купити на 100 руб буде 200 (бо теля коштує 0,5 руб). Тобто, простір перебору буде такий: 0<=t<=200. Але всього потрібно купити 100 голів скота, тому 0<=t<=100.
  5. З цього простору перебору будемо вибирати дані за деякими умовами:
  6. Тоді програма буде така:
    ПрограмаРезультат роботи

    1 9 90
    
  7. Ця програма виконає 11*21*101=23331 перевірок. Спробуємо їх зменшити. Якщо відома кількість биків та корів, то кількість телят легко підрахувати: t=100-(b+k). Тепер цикл по t можна відкинути. Програма буде така:
    ПрограмаРезультат роботи

    1 9 90
    
  8. Ця програма виконає 11*21=231 перевірку, що значно менше.

Приклад 3

У рівності КНИГА*3 = НАУКА замініть літери цифрами так, щоб рівність була вірна. КНИГА и НАУКА – п'ятизначні числа (наприклад, КНИГА =К*10000+Н*1000+И*100+Г*10+А). Однаковим літерам повинні відповідати однакові цифри, різним – різні. Якщо це можливо, виведіть вірну рівність на екран. Якщо ні, то вивести повідомлення про це.

Змінні:

Вихідні:

Алгоритм та програма

  1. Задачу будемо розв’язувати методом перебору. Спочатку з’ясуємо, які значення можуть приймати змінні k, n, i, g, a, y(простір перебору).
  2. Цифри k та n - перши цифри п'ятизначного числа. Вони не можуть бути 0. Тобто, простір перебору цих цифр буде такий: 1<=k,n<=9.
  3. Всі інші цифри можуть бути будь-якими, тобто від 0 до 9. Тобто, простір перебору інших цифр буде такий: 0<=i,g,a,y<=9.
  4. З цього простору перебору будемо вибирати дані за деякими умовами:
  5. Якщо будуть виконані всі умови і буде знайдено потрібний варіант, то змінній p присвоюється значення true.
  6. Наприкінці програми значення p перевіряється, і якщо p=false виводиться повідомлення, що перебір не дав результатів.
  7. Програма буде така:
    ПрограмаРезультат роботи

    28375*3=85125
    

    На цьому прикладі ясна загальна структура вирішення завдань на перебір варіантів. Для організації перебору використовуються вкладені цикли. Таких циклів стільки, скільки змінних може набувати різних значень. Кожен цикл відповідає розгляду одного з варіантів. Усередині циклу знаходиться перевірка, чи підходить даний варіант під умову завдання. Вирішуючи завдання методом повного перебору, завжди слід подумати, а чи не можна якимсь чином скоротити кількість варіантів, що перебіраються.

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

    Варіант 1

    1. Знайдіть розміри всіх паралелепіпедів, об’єм яких дорівнює числу V, та довжини сторін є натуральні числа. Рішення, які утворюються переставленням значень ребер виводити один раз. Наприклад, V=6, тоді рішенням задачі будуть такі набори чисел: (1, 1, 6), (1, 2, 3)
    2. У рівності АВ+ВС+СА=АВС замініть літери цифрами так, щоб рівність була вірна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть вірну рівність на екран.

    Варіант 2

    1. Дано натуральне число n. Чи можна представити його у вигляді суми квадратів двох натуральних чисел? Якщо ні, то вивести повідомлення про це. Якщо можна, то вивести значення на екран, причому рішення які утворюються переставленням чисел виводити один раз.
    2. У рівності ЛО*С=ОСЬ замініть літери цифрами так, щоб рівність була вірна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть вірні рівності на екран.

    Варіант 3

    1. У касі в необмеженій кількості є купюри по 3 та 5 руб. Скількома способами можна видати деяку суму S? Вивести всі варіанти та підрахувати їх кількість.
    2. У рівності КОКА + КОЛА = ВОДА замініть літери цифрами так, щоб рівність була вірна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть вірну рівность на екран.

    Варіант 4

    1. Знайти всі натуральні рішення рівняння x2+y2=k2, де x, y та k знаходяться в інтервалі від 1 до 30. Рішення які утворюються переставленням чисел x та y виводити один раз
    2. У рівності ТРИ + ТРИ + ТРИ = ДЫРА, причему (Ы + Ы) : Ы = Ы замініть літери цифрами так, щоб рівність була вірна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть вірну рівність на екран.

    Варіант 5

    1. У тарганів та павуків разом 74 лапки. Скільки може бути тарганів та павуків, якщо у таргана – 6 лапок, а у павука 8 (вивести всі можливі варіанти).
    2. У рівності ТРИ * ТРИ = ШЕСТЬ замініть літери цифрами так, щоб рівність була вірна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть вірні рівності на екран.

    Варіант 6

    1. Приписати до числа 1022 зліва та справа по одній цифрі так, щоб отримане шестизначне число було кратне 7, 8 та 9. Вивести отримане число на екран.
    2. У рівності ТЭТА + БЭТА = ГАММА замініть літери цифрами так, щоб рівність була вірна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть вірну рівність на екран.

    Варіант 7

    1. У тарганів та павуків разом 50 лапок. Скільки може бути тарганів та павуків, якщо у таргана – 6 лапок, а у павука 8 (вивести всі можливі варіанти).
    2. У рівності БУКВА • 6 = СЛОВО замініть літери цифрами так, щоб рівність була вірна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть вірну рівність на екран.

    Варіант 8

    1. Приписати до числа 102 зліва та справа по одній цифрі так, щоб отримане п’ятизначне число було кратне 4, 5 та 6. Вивести отримане число на екран.
    2. У рівності УДАР + УДАР = ДРАКА замініть літери цифрами так, щоб рівність була вірна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть вірну рівність на екран.

    Варіант 9

    1. Вартість відправлення посилки N грн. В наявності є марки за вартістю 1, 5, 10 гривень. Чи можна цими марками оплатити відправлення посилки при умові, що кількість марок не перевищує 5 штук (вивести всі можливі варіанти та їх кількість). Якщо не можна, то вивести повідомлення про це.
    2. У рівності МОСЬКА : И = ШАВКА замініть літери цифрами так, щоб рівність була вірна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть вірну рівність на екран.

    Варіант 10

    1. Знайдіть двозначне число, перша цифра якого дорівнює різниці між цим числом і числом, записаним тими ж цифрами, але в зворотному порядку.
    2. У рівності Г+О=Л-О=В*О=Л-О=М-К=А замініть літери цифрами так, щоб рівності були вірні. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть вірні рівності на екран.

    Варіант 11

    1. У тризначному числі закреслили першу зліва цифру; отримане двозначне число помножили на 7. В результаті вийшло вхідне тризначне число. Яке?
    2. У рівності СТО+ СОТ= ТОС замініть літери цифрами так, щоб рівність була вірна. СТО, СОТ и ТОС – трьохзначні числа (наприклад, СТО=С*100+Т*10+О). Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть вірну рівність на екран.

    Варіант 12

    1. В касі є монети по 2, 5 та 10 коп. Чи можна цими монетами видати суму Sum (вивести всі можливі варіанти та їх кількість)? Якщо не можна, то вивести повідомлення про це.
    2. Скільки булок було у пекаря? Відповіддю служить найменше можливе число «много» в ребусі
      БУЛОК + БЫЛО = МНОГО

    Варіант 13

    1. Коли тризначне число, дві перші цифри якого однакові, а третя дорівнює 5, розділили на однозначне число, то в залишку отримали 8. Знайти ділиме, дільник і частку.
    2. У рівності ab*ck=bbb замініть літери цифрами так, щоб рівність була вірна. Тут ab та ck двохзначні числа, а bbb трьохзначне число(ab=a*10+b, bbb=b*100+b*10+b). Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть всі варіанти вірних рівностей на екран.

    Варіант 14

    1. Є по одній гирі вагою по 100, 200, 300, 500, 1000, 1200, 1400, 1500, 2000 и 3000 г. Чи можна цими гирями зважити предмет вагою в n грамм? (вивести всі можливі варіанти та їх кількість)? Якщо не можна, то вивести повідомлення про це.
    2. У рівності ПОДАЙ — ВОДЫ = ПАША замініть літери цифрами так, щоб рівність була вірна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть вірну рівність на екран.

    Варіант 15

    1. У рівності a1+2b=cd замініть літери цифрами так, щоб рівність була вірна. Тут a1, 2b та cd двохзначні числа(a1=a*10+1, 2b=2*10+b, cd=c*10+d). Однаковим літерам повинні відповідати однакові цифри, різним – різні (ясно, що a, b, c, d <>1 та <>2 ). Виведіть всі варіанти вірних рівностей на екран та підрахуйте їх кількість.
    2. У рівності СО=РОКА замініть літери цифрами так, щоб рівність була вірна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть вірну рівність на екран.

    Варіант 16

    1. У рівності abcd+befd=edfbg замініть літери цифрами так, щоб рівність була вірна. Тут abcd, befd чотирьохзначні числа, а edfbg п’ятизначне число (наприклад, abcd=a*1000+b*100+c*10+d, а edfbg=e*10000+d*1000+f*100+b*10+g). Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть всі можливі варіанти вірних рівностей на екран.
    2. У рівності БУК=АШКА замініть літери цифрами так, щоб рівність була вірна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть вірну рівність на екран.

    Варіант 17

    1. Надрукуйте щасливі номери трамвайних білетів, які дорівнюють квадрату будь-якого натурального числа. Шестизначний номер білету називається щасливим, якщо сума перших трьох цифр дорівнює сумі останніх трьох цифр. Вивести на екран номер білету та число, квадратом якого він є, по 5 пар у рядку. Наприклад:
      108900 330 122500 350 128164 358 137641 371 155236 394
      173056 416 185761 431 203401 451 206116 454 216225 465
      ...
    2. У рівності МАМ=ОНТЫ замініть літери цифрами так, щоб рівність була вірна. Однаковим літерам повинні відповідати однакові цифри, різним – різні. Виведіть вірну рівність на екран.

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