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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.67
АлександрШ
2 / 2 / 0
Регистрация: 11.12.2010
Сообщений: 16
#1

Жадный алгоритм - C++

13.12.2010, 08:31. Просмотров 2789. Ответов 2
Метки нет (Все метки)

Нужно сделать проверку на правильность жадного алгоритма, доказать, что его решение единственно правильное. Кто знает? вот вполне рабочий код с жадным алгоритмом.
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
68
69
#include <stdio.h>
#include <iostream>
 
using namespace std;
 
int max(double* m, int n) {
  double max;
  int i, k;
  max = m[0];
  for (i=1;i<n;i++)
    if (max < *(m+i)){
      max = *(m+i);
      k = i;
    }
  return k;
}
 
int main() {
  double b = 0;
  cout << "Введите время срочного выполнения: ";
  cin >> b;
 
  int n = 0;
  cout << "Количество заказов: ";
  cin >> n;
 
  double m[n];
  double min_el, min_r, temp, sum, time;
  int mk[n];
  int i, j, k;
  double a[] = {8, 3, 7, 5, 9, 4};
  double c[] = {12, 10, 8, 9, 16, 20};
  // формирование массива отношений времени к прибыли
  for(i=0;i<n;i++) {
    m[i] = a[i] / c[i];
  }
 
 min_el = 0;
  for(j=0;j<n;j++) {
    min_r = m[max(m, n)] - min_el;
    for(i=0;i<n;i++){
      temp = m[i] - min_el;
      if((temp > 0) && (min_r >= temp)) {
        min_r = temp;
        k = i;
      }
    }
    mk[j] = k;
    min_el = m[k];
  }
 
  // подсчёт и вывод результатов
  sum = 0;
  time = 0;
  cout << endl;
  cout << "Выполняйте заказы с номерами:";
  for(i=0;i<n;i++) {
    if((time + a[mk[i]]) <= b) {
      cout << " " << mk[i] + 1;
      time += a[mk[i]];
      sum += c[mk[i]];
    }
  }
  cout << endl;
  cout << "Прибыль: " << sum << endl;
  cout << "Время: " << time << endl;
  return 0;
 
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.12.2010, 08:31
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Жадный алгоритм (C++):

Жадный алгоритм - C++
Добрый день. Помогите, пожалуйста, понять, где затаилась ошибка. Это задачка на жадный алгоритм: пользователь вводит размер...

Жадный алгоритм С++ - C++
С целью борьбы с теневой экономикой банк решил внедрить объединение N счетов фирмы в один. За одну операцию объединяются 2 счета и банк...

Жадный алгоритм - C++
Суть задачи - имеется N предметов различного размера. Один ящик имеет строгую вместимость. Необходимо разложить все N предметов в...

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

Жадный граф/алгоритм - C++
Требуется написать программу с графическим интерфейсом: пользователь задаёт точки (A, B, C и т.д.). Далее соединяет между собой какие-то...

Жадный алгоритм на графе - C++
Собственно, нужно написать программу поиска кратчайшего пути на графе &quot;жадным методом&quot;. То есть, дан ориентированный взвешенный граф (можно...

2
АлександрШ
2 / 2 / 0
Регистрация: 11.12.2010
Сообщений: 16
14.12.2010, 12:28  [ТС] #2
Выводит ошибку сегментирования, если берешь небольшие массивы, из двух-трех элементов. помогите разобраться?
0
светлана1990
0 / 0 / 0
Регистрация: 18.03.2012
Сообщений: 7
18.03.2012, 16:56 #3
Выложите пожалуйста полный код на С++ жадного алгоритма...очень надо(
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.03.2012, 16:56
Привет! Вот еще темы с ответами:

Жадный алгоритм (рюкзак) - C++
слишком медленно, но верно работает программа. Помогите пожалуйста ускорить. (извиняюсь за транслит или что-то похожее на него) ...

Жадный алгоритм сортировки массива(динамический) - C++
Здравствуйте, учусь работать с сортировками массивов, в данном случае жадный алгоритм. Алгоритм работы(): Ввод размера массива -&gt;...

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

Жадный алгоритм нахождения абсолютной разницы чисел - C++
Вот мое задание: А вот мой код: #include &lt;cstdlib&gt; #include &lt;iostream&gt; #include &lt;stdio.h&gt; using namespace...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

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