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

1. Розробити блок-схему алгоритму розв’язку завдання, згідно свого варіанту.
2. Написати код програми для розв’язку поставленого завдання на мові С.
3. Оформити звіт по роботі. Звіт повинен містити тему та мету роботи, код написаної програми та блок-схему алгоритму.

Індивідуальне завдання

Простий рівень

Завдання 1. Mario

В кінці World 1-1 у Nintendo’s Super Mario Brothers, Маріо повинен піднятися на півпіраміду з блоків (рис. 2.12), перш ніж стрибати (якщо він хоче максимізувати свій бал) у напрямку до флагштоку.

Рисунок 2.12 – Півпіраміда з блоків у грі Super Mario Brothers

Напишіть програму, яка відтворює цю півпіраміду за допомогою хешей (#) в якості блоків.

Спочатку користувач повинен ввести висоту півпіраміди, це невід'ємне ціле число не більше 23. (Висота півпіраміди, наведеної на рис. 2.12 становить 8). Якщо користувач не вводить потрібного значення – необхідно повторно вивести запит.

Особливу увагу варто звернути на вирівнювання піраміди. Результат роботи програми для висоти 4 повинен виглядати наступним чином:

         ##

      ###

   ####

#####

 

Завдання 2. Кавомат

При видачі решти з кавового автомату, він намагається мінімізувати кількість монет, які видає для кожного клієнта.

Наприклад, якщо для певного клієнта потрібно видати решту в 40 копійок, найбільша можлива монета для видачі решти становитиме 25 копійок. Після цього залишиться 15 копійок, оскільки 40 - 25 = 15. Ще 25 копійок автомат видати не може – це буде забагато, а тому наступна монета буде номіналом 10 копійок, залишивши в підсумку 5 копійок. Автомат видає ще 5 копійок і задача на цьому вирішена. Клієнт отримує одну монету номіналом 25 копійок, одну – 10 та ще одну – 5 копійок: всього три монети.

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

Для отримання суми решти буде використовуватися get_float() з бібліотеки CS50, щоб отримати на вході дані від користувача та printf з бібліотеки stdio, щоб вивести відповідь. Припустимо, що єдиними доступними монетами є 50, 25, 10 та 5 копійок.

Потрібно використовувати саме get_float(), щоб працювати з гривнями та копійками. Іншими словами, щоб можна було ввести здачу 9,75 гривень, програма буде приймати значення як 9,75 грн, а не 975 копійок.

Варто врахувати, щоб введена сума була кратна 5 копійкам, оскільки видати здачу 0,73 грн без монет номіналом 1 та 2 неможливо.

Результатом виконання програми повинна бути кількість монет, якими буде видана решта – ціле число.

Рекомендується, для зручності, введене значення з гривень перевести в копійки (ціле число). Однак тут варто враховувати правильність заокруглення до цілого.

 

Складний рівень

Завдання 1. Mario

На початку World 1-1 у Nintendo’s Super Mario Brothers, Маріо повинен перестрибнути дві півпіраміди з блоків (рис. 2.13), коли він рухається до флагштоку.

Рисунок 2.13 – Півпіраміди з блоків у грі Super Mario Brothers

 Напишіть програму, яка відтворює ці півпіраміди за допомогою хешей (#) в якості блоків.

Спочатку користувач повинен ввести висоту півпірамід, невід'ємне ціле число не більше 23. (Висота півпірамід, наведеної на рис. 2.13 становить 4, розрив між півпірамідами – 2). Якщо користувач не вводить потрібного значення – необхідно повторно вивести запит.

Особливу увагу варто звернути на вирівнювання піраміди. Результат роботи програми для висоти 4 повинен виглядати наступним чином:

         ##    #

      ###    ##

   ####    ###

#####    ####

 

Завдання 2. Картка

Практично всі зараз мають кредитну або платіжну картку. Ця картка має номер, нанесений на лицевій стороні та вбудований у магнітну смужку на обороті. Цей номер також зберігається в базі даних. Картками користується багато людей, тому ці номери досить довгі: MasterCard використовує 16-значні номери, а Visa використовує 13- і 16-значні номери. І це десяткові числа (від 0 до 9).

Однак насправді номери карток мають певну структуру. Номери MasterCard починаються з 51, 52, 53, 54 або 55; номери Visa починаються з 4. Але ці номери також мають в собі «контрольну суму». Ця контрольна сума дає змогу виявляти помилки (наприклад, перестановки), якщо це шахрайські номери, без необхідності запитувати базу даних, щоб зекономити час.

Більшість карток використовують алгоритм, винайдений Гансом Пітером Лунем. Згідно з алгоритмом Луна, можна визначити, чи дійсно номер картки (синтаксично) дійсний наступним чином:

1. Помножити кожну першу цифру на 2 та додати цифри цих добутків разом.
2. Додати до суми цифри, які не були помножені на 2.
3. Якщо остання цифра суми дорівнює 0 (остача від ділення на 10 рівна 0), номер дійсний!

Наприклад: 4561 2612 1234 5467.

Підкреслимо кожну першу цифру:

4561 2612 1234 5467

Множимо кожну з підкреслених цифр на 2:

4 • 2 + 6 • 2 + 2 • 2 + 1 • 2 + 1 • 2 + 3 • 2 + 5 • 2 + 6 • 2

Це дає наступне:

8 + 12 + 4 + 2 + 2 + 6 + 10 + 12

Додаємо цифри цих добутків (не самі добутки) разом:

8 + 1 + 2 + 4 + 2 + 2 + 6 + 1 + 0 + 1 + 2 = 29

Додаємо цю суму (29) до суми цифр, які не були помножені на 2:

29 + 5 + 1 + 6 + 2 + 2 + 4 + 4 + 7 = 60

Так як остання цифра в цій сумі (60) є нуль, то картка є дійсною!

Напишіть програму, яка запитує в користувача номер платіжної картки (16 цифр), а потім повідомляє, чи є цей номер картки діййсний та до якої платіжної системи належить (MasterCard або Visa).

Для зручності припустимо, що вводитись буде цілочисельне значення (тобто не буде дефісів чи пробілів, які можуть бути надруковані на картці).

Рекомендується використовувати функцію get_long_long з бібліотеки CS50 для отримання даних від користувача.