Задача
Полоска бумаги имеет размеры [latex]A×B[/latex]. Каждый раз от нее отрезается квадрат максимального размера до тех пор, пока не получится квадрат. Сколько квадратов получится?
Входные данные
Программе даны числа [latex]A[/latex] и [latex]B[/latex] [latex](1 ≤ A, B ≤ 10^9).[/latex]
Выходные данные
Требуется вывести количество квадратов.
Тесты
| Входные данные | Выходные данные |
|---|---|
| 12 4 | 3 |
| 15 3 | 5 |
| 20 20 | 1 |
| 8 12 | 3 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> using namespace std; int main() { int a, b, temp = 0; bool need = 1; cin >> a >> b; while (need) { if (a >= b) { temp = temp + a / b; a = a%b; } else { temp = temp + b / a; b = b%a; } if (a == 0 || b == 0) { need = 0; } } cout << temp; return 0; } |
Решение задачи
Нам было дана высота и ширина полоски бумаги. Есть три варианта:
- Высота равна ширине
- Высота больше ширины
- Высота меньше ширины
В первом случае нам надо вывести на экран единицу. Во втором случаем начинаем вычитать a - b до того момента, как a не будет меньше b или a не будет равняться 0. В третьем случае начинаем вычитать b - a до того момента, как b не будет меньше a или b не будет равняться 0.