Форум программистов, компьютерный форум, киберфорум
Наши страницы

НОЧД и НОНД(задача) - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Указатель на объект.объясните http://www.cyberforum.ru/cpp-beginners/thread631402.html
base - это базовый класс...first - это производный от base...iam() виртуальная функция, перегруженная в first... Вопрос: почему вызывается функция базового класса, а не first?.. #include <iostream>...
C++ GetModuleFileNameEx ошибка #include <iostream> #include <windows.h> #include <time.h> #include "main.h" #pragma comment(lib,"Psapi") using namespace std; //global ULONG crc_tab; http://www.cyberforum.ru/cpp-beginners/thread631400.html
C++ Отсортировать по возрастанию элементы массива
1)Дан массив целых чисел из 10 элементов отсортировать по возрастанию. 2)Дан действительный массив A.Напечатать индекс его отрицательных элементов. помогите пожалуйста написать программу на С++
Перевод программы с Pascal на С++ C++
uses crt; var i :integer; BEGIN ClrScr; Write('Результат: '); for i := 20 to 50 do if (i mod 3 = 0) and (i mod 5 <> 0) then Write(i, ' '); Readln; END.
C++ Квадратные уровнения http://www.cyberforum.ru/cpp-beginners/thread631379.html
помогите написать код. программа должна: решить квадратное уравнение по трем коэффициентам. даны a, b и c напишите как можно это реализовать.
C++ Рекурсия: нахождение биномиальных коэффициентов В общем нужно вывести биноминальные коэффициенты последовательности.... т.е есть последовательность - скажем вектор 12345 n = size = 5 k - пусть равен 2 тогда результатом должны быть все... подробнее

Показать сообщение отдельно
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
01.08.2012, 00:20
Судя по тому, что оно вылетело по таймлимиту, у вас больно долго вычитается из чисел по одной двойке (циклы 27–35 и 41–49). Это уж больно неэффективный способ найти, например, наибольший общий нечётный делитель каких-нибудь чисел вида 2na и 2nb, где a и b взаимно простые числа (GCD(a, b) = 1), а n в районе так 20. Быстрее сократить эти степени, а потом найти НОД маленьких чисел, а вы же ищете сначала их НОД (который выходит размером в миллион-другой), а потом начинаете мучительно из него вычитать по двойке (выполняя на каждой из полумиллиона итераций два [мееедленных] деления на большие числа), пока не дойдёте до заветной единицы.

Так что существенное различие: мы не перебираем варианты, пока не наткнёмся на подходящее число (тратя O(N) времени), а с помощью свойств функций сводим за O(1) задачу к вычислению НОД, а эта задача вычисляется за O(log N) операций (итого O(log N) времени на всё).
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru