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

как реализовать на с++ - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Дана целочисленна прямоугольная матрица. Определить количество строк, не содержащих ни одного нулевого элемента. http://www.cyberforum.ru/cpp-beginners/thread375950.html
Выполнить задание, используя динамическое выделение памяти. Дана целочисленна прямоугольная матрица. Определить количество строк, не содержащих ни одного нулевого элемента. Зарание большое спасибо)))) 2.3 Создавайте темы с осмысленными и понятными названиями - это серьезно повышает шансы, что на ваш вопрос ответят. 3.3 Запрещено создавать темы с бессмысленными названиями вроде "Помогите!",...
C++ пример из книги страуструпа struct pair { char* name; // ñòðîêà int val; // öåëîå }; const int large = 1024; static pair vec; pair* find(const char* p) { http://www.cyberforum.ru/cpp-beginners/thread375949.html
C++ Даны три положительных числа а, b, с. Проверить, будут ли они сторонами треугольника. Если да, то вычислить площадь этого треугольника.
Помогите, пожалуйста, исправить здесь ошибку времени... #include<iostream> #include<cmath> using namespace std; void main() { double a, b, c, s, p; cout<<"Vvedite a, b, c: "; cin>>a>>b>>c; if(a+b<=c||a+c<=b||b+c<=a) cout<<"treygilnik nevozmozhen"<<endl; else{cout<<"treygolnik vozmozhen"<<endl;
проверка нажатия клавиши C++
Всем привет, начал писать прогу и нет времени искать что либо в интернете... Кто помнит как как проверить что нажата клавиша 1 ?? Смысл такой пользователю предоставляется выбор 1: ---- 2:---- вроде же press key функция есть??
C++ Ноли вместо значений и нерабочий рандом, запутался с типами данных http://www.cyberforum.ru/cpp-beginners/thread375915.html
#include <stdio.h> #include <conio.h> #include <math.h> #include <cstdlib> #include <ctime> int main() { FILE *in;//ôàéë èñõîäíûõ äïííûõ FILE *out;// ôàéë íà çàïèñü
C++ помогите написать программу пожалуйста, срочно нужна В файле находятся только целые числа. Определить, имеет ли последовательность чисел, находящихся в файле, нечетную длинну, если да, то переменной middle присвоить значение среднего элемента файла. В противном случае присвоить этой переменной значение первого числа файла подробнее

Показать сообщение отдельно
*krIsTiNa*
0 / 0 / 0
Регистрация: 19.01.2011
Сообщений: 46
01.11.2011, 11:02     как реализовать на с++
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
procedure KOMMI(i);
 begin
  for y Є ЗАПИСЬ[X[i-1]] do
  if cost + A[X[i-1], y] < OptCost then
   if (i = n+1) AND (y = k) then
    begin OptX:=X; OptCost:= cost + A[X[i-1],y] end
   else if DOP[y] then
    begin 
     X[i]:=y; DOP[y]:= ложь;
     cost:=cost + A[X[i-1], y];
     KOMMI(i+1);
     DOP[y]:= истина; cost:=cost — A[X[i-1], y];
    end;
 end; {KOMMI }
 
 
begin { основная программа }
 for v Є V do DOP[v]:=истина;
 X[1]:=k; { k — произвольная }
 DOP[k]:= ложь;
 cost:=0; OptCost:= +бесконечность(большое число);;
 KOMMI(2);
end.
ЗАДАЧА КОММИВОЯЖЕРА
Пусть заданы конечное множество C городов, целые положительные расстояния A(c1,c2) для каждой пары городов c1,c2.
Требуется найти маршрут минимальной длины, проходящий через все города ровно один раз и возвращающийся в исходный пункт.
Это — задача на минимум. Карта представляется графом, ребрам которого приписаны веса. Из всех гамильтоновых циклов (это полный граф, в нем существуют гамильтоновы циклы) в этом графе нужно выбрать цикл минимальной длины. Длина определяется естественным образом — как сумма расстояний между городами, входящими в маршрут. Можно поступить просто — сгенерировать алгоритмом с возвратом все циклы и среди них выбрать минимальный. Однако немного изменив общую схему алгоритма с возвратом, можно добиться того, что возвраты будут происходить значительно раньше, и решение будет найдено быстрее.
Итак, задача на минимум — среди всех допустимых объектов ищется минимальный.
Каждому решению( и полному, и частичному ) приписывается стоимость — ее еще называют целевой функцией. Будем обозначать ее cost.
При продолжении решения стоимость может только увеличиваться:
cost(< X(1), … , X(i-1) >)<= cost(< X(1), … , X(i-1), X(i)>).
Для задачи коммивояжера целевой функцией, удовлетворяющей такому условию, будет
cost(< X(1), … , X(i)>)=A(X(1), X(2))+…+ A(X(i-1), X(i)).
Очевидно, что ее значение будет увеличиваться при удлинении маршрута.
Идея алгоритма:
1. Находим первое решение и запоминаем его стоимость в OptCost.
2. Пусть < X(1), … , X(i)> — текущее частичное решение. Прежде, чем пытаться продолжать его дальше, проверим, имеет ли смысл это делать. Если cost(< X(1), … , X(i)>) >= OptCost,
то любое его продолжение будет заведомо больше текущего минимального решения. Производим возврат к предыдущему частичному решению < X(1), … , X(i-1)>.
Таким образом, произведя «досрочный» возврат, мы избавляем себя от генерации всех заведомо неоптимальных продолжений, т.е. обрубаем целое поддерево на дереве поиска.
АЛГОРИТМ. {Нахождение гамильтоновых цикла min длины}
Данные: Граф G=<V,E>, представленный списками ЗАПИСЬ[v], матрица весов A[u,v].
Результаты: Печать min гамильтонова цикла.
Переменные ЗАПИСЬ, X, cost, OptX, OptCost, DOP — глобальные.

Добавлено через 16 минут
вот мой алгоритм на паскале
Pascal
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
70
const
 n0=100; {вершины}
 inf=32000;{бесконечность}
var
 m:integer; {рёбра}
 n:byte; {вершины}
 A:array[1..n0,1..n0] of real; {матрица весов}
 DOP:array[1..n0] of boolean; {допустимость вершины}
 X,OptX:array[1..n0] of byte; {маршруты}
 Cost,OptCost:real; {стоимости}
 r:real;
 i,j,k:byte;
 
procedure path(i:byte);
var u,j,v:byte;
begin
  for u:=1 to n do
    if (A[X[i-1],u]<inf) AND (Cost+A[X[i-1],u] < OptCost) then
      begin
        if (i=n+1) AND (u=1) then {новый минимум}
          begin
            for j:=1 to n do OptX[j]:=X[j];
            OptCost:=Cost+A[X[i-1],u];
          end
        else if DOP[u] then {продолжаем текущий маршрут}
          begin
            X[i]:=u; DOP[u]:=false;
            Cost:=Cost+A[X[i-1],u];
            path(i+1);
            {возврат, удаляем u из текущего маршрута}
            DOP[u]:=true;
            Cost:=Cost-A[X[i-1],u];
          end;
      end;
end;
 
BEGIN {main}
  for i:=1 to n0 do
  for j:=1 to n0 do
    A[i,j]:=inf;
 
  for i:=1 to n0 do
    begin
      DOP[i]:=true;
      X[i]:=0;
      OptX[i]:=0;
    end;
  Cost:=0; OptCost:=inf;
 
  Write('Vvedite kolvo vershin n= '); readln(n);
  Write('Vvedite kolvo reber m= '); readln(m);
  for i:=1 to m do
  begin
    Write('Vvedit cherez probil vershini i ves ',i,' rebra: '); Readln(j,k,r);
    A[j,k]:=r;
    A[k,j]:=r;
  end;
  X[1]:=1; DOP[1]:=false;
  path(2);
  if OptCost< inf then
  begin
    Writeln('OptCost', OptCost:5:2);
    for i:=1 to n do
      write(OptX[i],' ');
    writeln;
  end
  else
    writeln('No solution');
 readln;
END.
В программе граф неориентированный неполный. Заодно проверяется существование гамильтонова цикла.
Если граф полный, то число ребер m=n*(n-1)/2 и убирается проверка на существование ребра (A[X[i-1],u]<inf).
inf -бесконечность - число, большее длины самого дорогого пути.
Cost, OptCost - стоимости текущего и оптимального маршрута,
X, OptX - текущий и оптимальный маршрут.
DOP - допустимость вершины. Если вершина включена в текущий маршрут, то false.
path - рекурсия, которая осуществляет ветвление.

 Комментарий модератора 
Используйте теги форматирования кода
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 03:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru