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

Объяснить алгоритм просто перебора - 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++ подпрограмма удаление непарных элементов массива С++ Пожалуйста, срочно нужно, напишите код и желательно объяснить ... подробнее

Показать сообщение отдельно
lemegeton
2933 / 1362 / 136
Регистрация: 29.11.2010
Сообщений: 2,725
04.01.2013, 02:09
В лоб такие вещи решаются, конечно, но при количестве элементов массива большем, скажем, 12, ждать станет неприлично долго.

Концепт "в лоб" заключается в том, чтобы перебирая все возможные варианты находить оптимальный.
Пруф ов концепт.
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <iterator>
#include <numeric>
 
struct RandomGenerator {
  int operator()() const { return 1 + ((rand() % 5) ? rand() % 7 : 100 + rand() % 50); }
};
 
template<class Iterator>
double getBestSplitSize(Iterator begin, Iterator end) {
  double result = 0;
  while (begin != end) {
    result += *begin++;
  }
  return result / 2.0;
}
 
template <class Iterator>
Iterator getBestResult(Iterator begin, Iterator end, double ideal) {
  double result = 0.0;
  while (result + *begin < ideal || fabs(result + *begin - ideal) < 0.001) {
    result += *begin++;
  }
  return begin;  
}
 
int main(int argc, char *argv[]) {
  srand(time(0));
 
  int size = 12;
  int *stones = new int[size];
  
  std::generate(stones, stones + size, RandomGenerator());
  std::copy(stones, stones + size, std::ostream_iterator<int>(std::cout, " "));
  std::sort(stones, stones + size);
  std::cout << std::endl;
 
  double idealResult = getBestSplitSize(stones, stones + size);
  std::cout << "Ideal is " << idealResult << "." << std::endl;
 
  int *result = new int[size];
  int bestResult = 0;
  do {
    int thisResult = std::accumulate(stones, getBestResult(stones, stones + size, idealResult), 0);
    if (fabs(thisResult - idealResult) < fabs(bestResult - idealResult)) {
      bestResult = thisResult;
      std::copy(stones, stones + size, result);
    }
  } while (std::next_permutation(stones, stones + size));
  
  int *position = getBestResult(result, result + size, idealResult);
  std::copy(result, position, std::ostream_iterator<int>(std::cout, " "));
  std::cout << "= " << std::accumulate(result, position, 0) << std::endl;
  std::copy(position, result + size, std::ostream_iterator<int>(std::cout, " "));
  std::cout << "= " << std::accumulate(position, result + size, 0) << std::endl;
 
  delete [] result;
  delete [] stones;
 
  std::cin.peek();
  return 0;
}
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru