Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
supra7sky
15 / 15 / 1
Регистрация: 07.02.2013
Сообщений: 123
#1

Резать прямоугольник, пока от него не останутся только квадраты. Посчитать их количество. (Оптимизировать программу) - C++

03.11.2013, 19:47. Просмотров 497. Ответов 1
Метки нет (Все метки)

Есть прямоугольник A x B. Нужно отрезать от него как можно больший квадрат и отбросить его (ставя счетчик в +1). Оставшийся прямоугольник так же резать до тех пор, пока не останется квадрат.

Сделал два варианта:
Вывел формулу (в некоторых случаях работает неправильно):
C++
1
2
if (a > b) swap(a, b); // а всегда меньшая сторона
cnt = ( (a*b)/(a*a) ) + a*b - (a*a)*( (a*b)/(a*a) )
Код, который вроде бы работает правильно, но медленно:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
typedef long long longest;
 
int main()
{
    longest a, b, cnt = 0;
    cin >> a >> b;
 
    do {
        if (a > b) swap(a, b);
        b -= a;
        cnt++;
    } while(b != 0);
 
    cout << cnt;
    //system("pause");
    return 0;
}
Задача: уложится в определенное время, например 100 мс. Мне кажется здесь можно использовать формулу, но ее нужно переделать.
Ответы разнятся при числах а= 1 000 000 000, b = 1 100 000 000
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.11.2013, 19:47
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Резать прямоугольник, пока от него не останутся только квадраты. Посчитать их количество. (Оптимизировать программу) (C++):

Дан прямоугольник размерами 425х131. От него отрезают квадраты со стороной 131, пока это возможно - C#
Дан прямоугольник размерами 425х131. От него отрезают квадраты со стороной 131, пока это возможно.Затем от оставшегося прямоугольника вновь...

Дан прямоугольник с размерами aхb. От него отрезают квадраты максимального размера, пока это возможно - Pascal
Помогите решить пожалуйста, очень нужно:) Дан прямоугольник с размерами aхb. От него отрезают квадраты максимального размера, пока это...

C клавиатуры вводятся числа, пока не будет введено отрицательное число. Посчитать их количество - Turbo Pascal
Помогите,пожалуйста, разобраться) C клавиатуры вводятся числа, пока не будет введено отрицательное число. Посчитать их количество. ...

Вводите числа с клавиатуры, пока не будет введен ноль. Посчитать количество и сумму чисел - Pascal ABC
Вводите числа с клавиатуры, пока не будет введен ноль. Посчитать количество и сумму чисел.

Режем прямоугольник на квадраты - C++
Помогите пожалуйсто решить задачу :resent: Условие : Дан прямоугольник ( длину и ширину вводим с клавиатуры ) от него отрезают...

Вписать квадраты в прямоугольник - C#
Всем доброго времени суток. Дано задание: /*Подробно описать функцию перебора с возвратом, решающую следующую задачу: дано множество...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
chedman
81 / 80 / 2
Регистрация: 30.10.2013
Сообщений: 251
03.11.2013, 21:33 #2
может значение 1 000 000 000*1 100 000 000 зашкаливает

может в начале делить, а потом умножать
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.11.2013, 21:33
Привет! Вот еще темы с ответами:

разбить прямоугольник на квадраты - C++
здравствуйте! есть задание :Задан прямоугольник размером А*В (А и В - натуральные). От прямоугольника каждый раз отрезают квадраты...

Рекурсия: разбить прямоугольник на квадраты максимального размера - Pascal
Написать программу для решения задачи. Задан прямоугольник со сторонами а и в. Разбиваем его на части с помощью квадратов. Определить,...

Рекурсия: разбить прямоугольник на квадраты максимального размера - VBA
помогите пожалуйста Написать программу для решения задачи. Задан прямоугольник со сторонами а и в. Разбиваем его на части с помощью...

Можно ли расположить квадраты так, чтобы покрыть прямоугольник? - C#
перебора с возвратом, решающую следующую задачу: дано множество квадратов, общая площадь которых равна площади данного прямоугольника....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru