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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Написать программу, выводящую сумму и разность двух введенных чисел http://www.cyberforum.ru/cpp-beginners/thread751750.html
Написать программу, выводящую сумму и разность двух введенных чисел. Основная программа запрашивает два числа и передает их в функцию. Функция реализует вычисления и вывод на экран.Написать программу на СИ++. Добавлено через 2 часа 0 минут Помогите срочно надо
C++ Функция (удаление элементов вектора, равных переданному значению) Здравствуйте товарищи и С Новым Годом!!! Большую часть задания сделал, нужно еще кое что дополнить, все никак не соображу. Вообщем мне нужно, чтобы "Filter" удалял элементы вектора равные переданному значению т.е мне нужна еще одна функция , которая будет удалять например вектор "20". #include <iostream> #include <conio.h> using namespace std; struct vect { int length ; ... 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'а не втыкал - возможно там тоже самое.
 
Текущее время: 22:13. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru