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

Объяснить алгоритм просто перебора - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Написать программу, выводящую сумму и разность двух введенных чисел http://www.cyberforum.ru/cpp-beginners/thread751750.html
Написать программу, выводящую сумму и разность двух введенных чисел. Основная программа запрашивает два числа и передает их в функцию. Функция реализует вычисления и вывод на экран.Написать программу...
C++ Функция (удаление элементов вектора, равных переданному значению) Здравствуйте товарищи и С Новым Годом!!! Большую часть задания сделал, нужно еще кое что дополнить, все никак не соображу. Вообщем мне нужно, чтобы "Filter" удалял элементы вектора равные переданному... http://www.cyberforum.ru/cpp-beginners/thread751725.html
Вычислить значение выражения e^Sinx + ln (Sinx) C++
Добрый день, прошу помощи) Дано выражение: e^Sinx + ln (Sinx) наметки кода: #include "StdAfx.h" #include <math.h> #include <iostream.b> #include <conio.h> using namespace std; int main() {
C++ Написать программу, упорядочивающую массив строк в порядке убывания их длинны методом пузырьковой сортировки. Использовать указатели на строки.
Написать программу, упорядочивающую массив строк в порядке убывания их длинны методом пузырьковой сортировки. Использовать указатели на строки.
C++ Написать программу, использующую стандартную функцию сравнения строк для определения среди трех строк, вводимых пользователем, одинаковых. http://www.cyberforum.ru/cpp-beginners/thread751689.html
Написать программу, использующую стандартную функцию сравнения строк для определения среди трех строк, вводимых пользователем, одинаковых.
C++ подпрограмма удаление непарных элементов массива С++ Пожалуйста, срочно нужно, напишите код и желательно объяснить ... подробнее

Показать сообщение отдельно
suff1x
15 / 15 / 1
Регистрация: 26.09.2012
Сообщений: 70
04.01.2013, 03:32
посидел, придумал алгоритм (сразу с примером):

1. упорядочим любой исходный массив W по возрастанию (например получили, W = {1,1,2,3,3,3,4,8,9} )
2. создаем две накопительные переменные Wa, Wb (в них будем просчитывать суммы) и два массива heapA, heapB (тут будут номера камней).
3. в переменную Wa вносим значение W[N-2], Wb - значение W[N-1] (8 и 9 соответственно).
4. в массивы вносим позиции самых "тяжелых" значений heapA[0] = N-2, heapB[0] = N-1.
5. проходим for'ом со счетчиком позиции i по массиву W = {1,1,2,3,3,3,4,8,9} начиная с N-3 до 0:
- сравниваем Wa и Wb (т.е. в нашем примере 8 и 9)
- к меньшей либо равной суммовой переменной плюсуем значение W[i] (т.е. Wa+=4 в нашем примере для первой итерации).
- соответственно в массив heapA[N-i-2] (для позиционированния в массивах heap можно добавить предварительно еще переменные-инкременты - тут уже по желанию) вносим значение i (т.е. номер данного камня, который в кучу А в нашем случае попал).
6. получили два массива с номерами камней - по этим номерам можно определить веса камней по кучам и их перечислить итогом по группам.

ниже пару примеров вкратце обрисую итеративно (-1 в "кучковых" массивах - предварительно занесем в качестве признака отсутствия камня - это для примера, массивы эти правильней сделать динамическими естественно):

пример 1 (чуть подробнее):
позиция: 0,1,2,3,4,5,6,7,8
значение: 1,1,2,3,3,3,4,8,9
N = 9;

i=6) 8<9 -> Wa=8+4=12;Wb=9; heapA{7;6;-1;-1;-1;-1;-1;-1};heapB{8;-1;-1;-1;-1;-1;-1;-1}
i=5) 12>9 -> Wa=12;Wb=9+3=12; heapA{7;6;-1;-1;-1;-1;-1;-1};heapB{8;-1;5;-1;-1;-1;-1;-1}
i=4) 12=12 -> Wa=12+3=15;Wb=12; heapA{7;6;-1;4;-1;-1;-1;-1};heapB{8;-1;5;-1;-1;-1;-1;-1}
i=3) 15>12 -> Wa=15;Wb=12+3=15; heapA{7;6;-1;4;-1;-1;-1;-1};heapB{8;-1;5;-1;3;-1;-1;-1}
i=2) 15=15 -> Wa=15+2=17;Wb=15; heapA{7;6;-1;4;-1;2;-1;-1};heapB{8;-1;5;-1;3;-1;-1;-1}
i=1) 17>15 -> Wa=17;Wb=15+1=16; heapA{7;6;-1;4;-1;2;-1;-1};heapB{8;-1;5;-1;3;-1;1;-1}
i=0) 17>16 -> Wa=17;Wb=16+1=17; heapA{7;6;-1;4;-1;2;-1;-1};heapB{8;-1;5;-1;3;-1;1;0}

из полученных массивов heap соберем веса кучек:
куча А = 8+4+3+2 = 17
куча B = 9+3+3+1+1 = 17

пример 2 (сокращенно, думаю понятно будет):
позиция: 0,1,2,3,4,5,6,7
значение: 1,1,1,1,1,1,1,7

1,1,1,1,1,1,1,7
1,1,1,1,1,2,7
1,1,1,1,3,7
1,1,1,4,7
1,1,5,7
1,6,7
7,7

пример 3:

значение: 1,2,2,2,6,6,9,11

1,2,2,2,6,6,9,11
1,2,2,2,6,15,11
1,2,2,2,15,17
1,2,2,17,17
1,2,19,17
1,19,19
20,19

и т.п.

в теории алгоритм будет работать. завтра ради интереса напишу программный код (как там по скорости будет). наверняка доработать можно будет алгоритм. но, думаю, и этот будет правильно работать.

ps. автору темы спасибо за простую, но интересную задачку.
pps. в предыдущий код lemegeton'а не втыкал - возможно там тоже самое.
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru