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

Алгоритм цепочка (исправить код) - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Помогите дописать( исправить код) алгоритм http://www.cyberforum.ru/cpp-beginners/thread572539.html
Условие Некоторые компании являются совладельцами других компании, так как приобрели часть их акций. Говорят, что компания А контролирует компанию В, если имеет место по меньшей мере одно из следующих условий: · А=В; · А владеет более, чем 50% акций В; · А контролирует k (k>0) компаний С1,…,Сk таких, что компания Сi владеет соответственно Xi% акций компании В...
C++ Небольшой баг Дана очень простая задачка: Даны числа a0, X, Y, M. Рассмотрим бесконечную последовательность ai = (X * ai-1 + Y) mod M, где операция "a mod b" означает остаток от деления числа a на число b. Очевидно, что начиная с некоторой позиции, эта последовательность зацикливается. Ваша задача -- найти длину цикла, и количество первых элементов этой последовательности, которые не входят в цикл.... http://www.cyberforum.ru/cpp-beginners/thread572538.html
Структура. C++
Добрый вечер..пишу уже 3 раз=) Я сделал задание По умолчанию Картотека в бюро обмена квартир (связные списки, файлы и т.д.) Всем Здрасьте) Вот задание:Картотека в бюро обмена квартир организован как линейный список. Сведения о каждой квартире содержат: количество комнат; этаж;
Из 2ой в 10ую C++
Помогите, никак не догоню Задано неотрицательное целое число в двоичной системе счисления. Требуется перевести его в десятичную. Ввод В первой строке содержится исходное число не более чем из 50 000 цифр 0 и 1 без ведущих нулей. Вывод Вывод должен содержать это число в десятичной системе счисления без ведущих нулей. Ввод
C++ Разделить строку на две подстроки. http://www.cyberforum.ru/cpp-beginners/thread572482.html
Доброго времени суток.. В задании необходимо разбить исходную строку на две подстроки, при этом первая длиной k символов (если на k-ю позицию попадает слово, то его следует отнести ко второй строке). Вот, что вышло у меня: #include "stdafx.h" #include <iostream> #include <cstdlib> #include <string.h> using namespace std; int main()
C++ Функция не берёт значение переменной из программы Короче функция игнорирует переменные из программы. (переменные глобальные) вот код //#include <cstdlib> #include <iostream> #include <graphics.h> #include <stdio.h> #include <stdlib.h> using namespace std; char Metka; подробнее

Показать сообщение отдельно
Dima2202
0 / 0 / 0
Регистрация: 12.05.2012
Сообщений: 6
13.05.2012, 18:28     Алгоритм цепочка (исправить код)
Условие

Задан набор неповторяющихся пар (Ai,Aj), где Ai, Aj принадлежат множеству А={A1,A2,…,An}. Необходимо составить цепочку максимальной длины по следующему правилу:
(Ai,Aj)+(Aj,Ak)=(Ai,Ak).
При образовании этой цепочки любая пара может быть использована не более одного раза.

Входные данные

Входные данные находятся в файле input.in. Первая строка этого файла содержит два числа: n – размер множества A (элементы множества целые числа от 1 до n) и k – количество различных пар. Следующие k строк файла содержат по два элемента через пробел, которые задают очередную пару..

Выходные данные

Выходной файл output.out содержит две строки: первая строка – длина цепочки максимальной длины, в следующей строке указаны пары (Ai,Aj) в той последовательности, в которой они участвовали при образовании цепочки максимальной длины. Если цепочек такой длины несколько, то выдается та из них, которая лексикографически меньше.

Пример входных данных

5 5
1 2
4 3
1 5
2 3
5 4


Пример выходных данных

3
1 5
5 4
4 3

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
#include <stdio.h>
#define MAX_N 18
 
long a[MAX_N][2],n,m,i,j,t,out,outk;
char d[(1<<MAX_N)-1][MAX_N];
char q[1<<(MAX_N/2)];
FILE *w;
 
void inputdata()
{
    FILE *f = fopen("input.in","rt");
    fscanf(f,"%ld%ld",&m,&n);
    for (i=0;i<n;++i) fscanf(f,"%ld%ld",&a[i][0],&a[i][1]);
    fclose(f);
}
 
char f(long a)
{
    return q[(a>>m)]+q[a & ((1<<m)-1)];
}
 
void force(long x,long y)
{
    if (x==0) return;
    force(x-(1<<y),d[x][y]-1);
    fprintf(w,"%ld %ld\n",a[y][0],a[y][1]);
}
 
void outputdata()
{
    w = fopen("output.out","wt");
    fprintf(w,"%ld\n",f(out));
    force(out,outk);
    fclose(w);
}
 
void main()
{
    inputdata();
    m=n/2+(n & 1);
    for (i=0;i<1<<n;++i)
    {
        for (j=0;j<m;++j)
            if (i & (1<<j)) q[i]++;
    }
    for (i=0;i<n;++i) d[1<<i][i]=n+1;
    for (i=1;i<1<<n;++i)
        for (j=0;j<n;++j)
             if (d[i][j])
             {
                for (t=0;t<n;++t)
                    if ((i & (1<<t))==0 && (a[j][1]==a[t][0]))  
                        if (!d[i | (1<<t)][t]) d[i | (1<<t)][t]=j+1;
                if (f(i)>f(out))
                {
                    out=i;
                    outk=j;
                }
             }
    outputdata();
}
Добавлено через 20 часов 55 минут
моет просто ввод и вывод поменять?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 04:06. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru