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

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

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

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

03.11.2013, 19:47. Просмотров 485. Ответов 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++ Режем прямоугольник на квадраты
C++ разбить прямоугольник на квадраты
Выводить на экран квадраты чисел до тех пор, пока не будет введено число 0 C++
C++ Выводить на экран квадраты введенных чисел до тех пор, пока не будет введено число 0
Вводить с клавиатуры числа и выводить квадраты этих чисел до тех пор, пока не будет введено число 0 C++
C++ Вводить с клавиатуры целые числа (>0) и выводить на экран квадраты этих чисел до тех пор, пока не будет введено число 0. Использовать цикл do...while.
C++ Распечатать квадраты только 3-значных чисел от 1 до N
Дан прямоугольник с размерами 543x130 мм. Сколько квадратов со стороной 130 мм можно отрезать от него? C++
За один просмотр файла выбрать числа из него и посчитать среднее арифметическое C++
C++ Написать программу, которая рисует квадраты
C++ Создать программу, которая подсчитывает количество чисел в тексте и выводит на екран все слова, состоящие только из латинских букв
C++ Посчитать количество всех букв и количество вхождений каждой буквы

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
chedman
80 / 79 / 2
Регистрация: 30.10.2013
Сообщений: 250
03.11.2013, 21:33     Резать прямоугольник, пока от него не останутся только квадраты. Посчитать их количество. (Оптимизировать программу) #2
может значение 1 000 000 000*1 100 000 000 зашкаливает

может в начале делить, а потом умножать
Yandex
Объявления
03.11.2013, 21:33     Резать прямоугольник, пока от него не останутся только квадраты. Посчитать их количество. (Оптимизировать программу)
Ответ Создать тему
Опции темы

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