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

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

Войти
Регистрация
Восстановить пароль
 
Bringoff
СуперМодулятор
132 / 131 / 15
Регистрация: 03.11.2012
Сообщений: 974
#1

Оптимизировать перебор - C++

27.11.2012, 23:22. Просмотров 406. Ответов 2
Метки нет (Все метки)

Неделю учу С++, так что прошу не гадить. Надо уменьшить время работы.
Задача:
Кликните здесь для просмотра всего текста
Вступление
— Брат мой, Магистр Ордена хочет узнать завтра о результатах наших многолетних изысканий. Он хочет видеть, ни много, ни мало, Суммирующую Машину! Даже более того: он хочет, чтобы наша Машина — всего лишь машина — продемонстрировала свое постижение Таинства Суммы настолько глубоко, насколько это возможно. Он хочет, чтобы Машина нашла каких-нибудь два числа, дающих в сумме священное число 10000!
— Тс-с-с! Но это же безумство, граничащее с кощунством! Как Машина может ВЫЧИСЛИТЬ священное число? Двадцать семь лет мы работаем над ней, и смогли только лишь научить ее отвечать на вопрос: «Больше сумма двух введенных чисел, чем 10000, или меньше?». Но разве может смертный найти два таких числа, чтобы их сумма оказалась равна 10000?
— И все же нам придется сделать это с помощью нашей Машины, пусть она и неспособна на это. Иначе у нас будут… ну, скажем так, крупные неприятности, если кипящее масло можно назвать таким словом. Впрочем, у меня есть идея. Помнишь, на той неделе мы ввели в Машину числа −7 и 13, она ответила, что их Сумма меньше 10000. Я не знаю, как это проверить, но нам ничего не остается, как доверять созданию наших рук. Что, если теперь мы возьмем число большее, чем −7 и снова запустим Машину? И будем так делать снова и снова, пока не найдем такое число, которое в сумме с 13 даст 10000! Надо только подготовить список возрастающих чисел.
— Не верю я в эту идею… Давай лучше начнем с суммы, заведомо большей, чем Священное число и будем уменьшать одно из слагаемых, так у нас больше шансов избегнуть кипяще… крупных неприятностей.
Так ни о чём и не договорившись, Братья разошлись по своим кельям. К следующему дню, каждый из них подготовил такой список чисел, который, по его мнению, мог бы их спасти… Смогут ли спасти их оба списка вместе?
Задача
Ваша программа должна определять, можно ли из двух списков целых чисел выбрать по одному числу так, чтобы в сумме они составили 10000.
Исходные данные
Состоят из двух списков — одного, потом другого. Формат каждого из этих списков таков: в первой строчке записано количество Ni чисел в i-м списке, далее в Ni строчках по одному числу в строке записаны сами списки. Выполняются неравенства 1 ≤ Ni ≤ 50000, все элементы списков лежат в диапазоне от –32768 до 32767. Первый список упорядочен по возрастанию, второй — по убыванию.
Результат
На выходе следует записать YES, если из списков можно выбрать по числу, которые в сумме дадут 10000 и NO в противном случае.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;
 int main()
  {
        int nfirst,i;
        int first[50000];
        cin>>nfirst;
        
        for (i=1;i<=nfirst;i++)
        {
            cin>>first[i];
        }
        int nsecond;
        cin>>nsecond;
        i=1;
        int second[50000];
        for (i=1;i<=nsecond;i++)
        {
            cin>>second[i];
        }   
        int j=1;
        bool f;
        f=false;
        for (i=1;i<=nfirst;i++)
        {
            for (j=1;j<=nsecond;j++)
            {
                if (first[i]+second[j]==10000)
                {
                    f=true;
                    break;
                }
                if (f) break; 
            }
        }
        if (f)
            cout<<"YES";
            else cout<<"NO";
         return 0;   
        }
Выходит за предел времени. На паскале на 4-ом тесте, тут на 10-ом. Лимит - 1 секунда.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.11.2012, 23:22     Оптимизировать перебор
Посмотрите здесь:

Слишком долгий перебор - нужно оптимизировать - C++
Задача с ацмп.ру: Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок. Задача легкая, но в...

Оптимизировать код - C++
Доброго времени суток, как можно оптимизировать код что бы он быстрее работал ? Дана последовательность из n чисел a1, a2,..., an. C...

Оптимизировать код - C++
Первое число входного потока - количество чисел Дальше идут те самые числа Надо найти кол-во пар чисел, для которых выполняется nums &lt;=...

Оптимизировать алгоритм - C++
Приятель подкинул задачку: Получить новую матрицу В, элемент b которой равен наименьшему из элементов a исходной матрицы, где k меняется...

Оптимизировать функцию - C++
Помогите оптимизировать функцию она работает правильно только очень медленно :cry: уже несколько дней над ней сижу и ничего не выходит ...

Нужно оптимизировать - C++
Есть задание, есть готовый код. Но он не проходит скоростной режим, нужно оптимизировать, помогите плз) #include &lt;iostream&gt; ...

Оптимизировать и минимализировать код - C++
Cделал легкую прогу. Понимаю логики 0 в коде. Можете помочь оптимизировать код? А заодно и сделать код более минималистичным. #include...

Исправить и оптимизировать код - C++
нужна помощь по исправлению ошибок Написал программу она работает все отлично но препод сказал что она не очень красивая Помогите...

Оптимизировать вычисление формулы - C++
Добрый день Расчет совсем простой, float R = ((dotProduct(vec1, vec2) / length(vec1) + 1) / 2; return pow(R, 1 / 4.0);где...

Как оптимизировать код? - C++
Как оптимизировать код, чтобы работала программа быстрее #include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;iomanip&gt; using namespace...

Как оптимизировать код? - C++
Вот такой код, написанный для микроконтроллера импульсного блока питания. Просто интересно мнение, что можно поменять и изменить для...

Помогите оптимизировать код - C++
Помогите пожалуйста разобраться, хотелось бы чтобы это прграммка наконец-то заработала. Задача такая: Одномерный массив целых чисел,...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
yekka
385 / 149 / 8
Регистрация: 12.05.2011
Сообщений: 450
28.11.2012, 19:02     Оптимизировать перебор #2
http://ru.wikipedia.org/wiki/двоичный_поиск
Bringoff
СуперМодулятор
132 / 131 / 15
Регистрация: 03.11.2012
Сообщений: 974
28.11.2012, 19:06  [ТС]     Оптимизировать перебор #3
Почитаю, но уже помогли на паскале. Читаю второй список и сразу сравниваю. Тесты прошёл.
Ответ Создать тему
Опции темы

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