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

Рекурсия: составить цепочку максимальной длины по правилам игры "Города" - C++

Восстановить пароль Регистрация
 
art_stalker
0 / 0 / 0
Регистрация: 02.04.2010
Сообщений: 8
04.04.2010, 08:26     Рекурсия: составить цепочку максимальной длины по правилам игры "Города" #1
Задача: Задана последовательность названий городов. Составить цепочку максимальной длины по правилам известной игры: первым элементом цепочки может быть название любого города, каждый следующий начинается с последней буквы предыдущего, двух одинаковых городов в цепочки быть не должно.

Задача на рекурсию, подскажите как написать этот код, а то у меня идей совсем нет=(

Добавлено через 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
#include<stdio.h>
int a[4]={1,2,3,4};
int nl=4;
FILE *in;
void per(int *s,int n)
{
int d;
int i,j;
if(n>1)
{
per(s,n-1);
for(i=n-1;i>=1;i--)
{
d=s[n-1];
s[n-1]=s[i-1];
s[i-1]=d;
per(s,n-1);
d=s[n-1];
s[n-1]=s[i-1];
s[i-1]=d;
}
}
else
{
for(j=1;j=nl;j++)
fprintf(in,"%d",s[j-1]);
fprintf(in,"/n");
}
}
void main()
{
in=fopen("123.dan","w");
per(a,nl);
printf("\n");
}
Вот что смог написать, но этот код работает с цифрами, а не словами и он только выдает все возможные варианты перебора 4-х цифр.
И вот вопрос как код научить работать со словами, как найти буквы и вывести строчку самую длину после перебора всех вариантов. Подскажите пожалуйста буду очень благодарен и признателен=)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.04.2010, 08:26     Рекурсия: составить цепочку максимальной длины по правилам игры "Города"
Посмотрите здесь:

Найти отрезок максимальной длины в массиве А C++
C++ Слово максимальной длины заменить на слово минимальной длины
Массивы: создать цепочку символов «а» произвольной длины, после которой следует символ «b» C++
Поиск последовательности элементов максимальной длины в массиве C++
C++ Составить новый массив по некоторым правилам
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Vorona
Peace 2 all shining faces
 Аватар для Vorona
660 / 522 / 44
Регистрация: 05.03.2010
Сообщений: 1,256
04.04.2010, 11:07     Рекурсия: составить цепочку максимальной длины по правилам игры "Города" #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
#include <stdio.h>
 
int nl = 4;
char c[4] = {'a', 'b', 'c', 'd'};
 
FILE *in;
 
void per(char *s, int n){
    int d;
    int i, j;
    if(n > 1){
        per(s, n - 1);
        for(i = n - 1; i >= 1; i--){
            d = s[n - 1];
            s[n - 1] = s[i - 1];
            s[i - 1] = d;
            per(s, n - 1);
            d = s[n - 1];
            s[n - 1] = s[i - 1];
            s[i - 1] = d;
        }
    }
    else{
        for(j = 1; j <= nl; j++)
            fprintf(in, "%c", s[j - 1]);
        fprintf(in, "\n");
    }
}
 
void main(){
    in = fopen("C:\\123.dan","w");
    per(c, nl);
    printf("\n");
}
перебор букв)
длина строки - ф-ция strlen();
art_stalker
0 / 0 / 0
Регистрация: 02.04.2010
Сообщений: 8
04.04.2010, 11:21  [ТС]     Рекурсия: составить цепочку максимальной длины по правилам игры "Города" #3
Программа должна считывать города из текстового файла который на жеском диске и вывести их расположив по правилам игры.

Добавлено через 7 минут
Vorona идея мне понятна, перебор не так труден для меня,а вот как его сделать так чтобы он работал именно со словами и искал в них буквы по правилам и вывел именно ту строку в которой самая большая и правильная комбинация слов?
DmitrijN
0 / 0 / 0
Регистрация: 01.04.2010
Сообщений: 9
04.04.2010, 11:42     Рекурсия: составить цепочку максимальной длины по правилам игры "Города" #4
Каждое имя города - это таблица с \0 окончанием. Смотришь сначало конечную букву в слове, затем ищещь все возможные варианты и засовываешь их во временный массив указателей, далее можно использовать один из методов поиска приведенных на этом сайте. Но можно брать слово из временного массива и последовательно сравнивать его с тем массивом в котором у тебя уже есть несколько отсартированных городов и из которого ты собственно получил эту самую первую букву слова(опять же массив указателей). Если город встречается, пропускаем его и смотрим следующий и т.д. до тех пор пока не найдем нужный. Сравнение можно делать, например с помощью strcmp().
И после того как использовали указатели не забываем написать free(имя указателя).
Собственно вот. Я бы сделал так.
Да еще поиск буквы в слове и ее позиции можно сделать так: strspn() или что-нибудь в эту сторону.
Ты получишь позицию знака и далее по условию: первая буква в таблице создаешь тот самый темп массив указателей.

Добавлено через 3 минуты
Используй массив указателей.
Пример его создания:

C
1
2
3
4
5
6
7
8
9
10
11
char *s, str[]="Hello, world", *array[100];
 
s=(char *)malloc(sizeof(str));
 
strcpy(s, str);
 
array[0]=s;
 
//something being done
 
free(s);
Vorona
Peace 2 all shining faces
 Аватар для Vorona
660 / 522 / 44
Регистрация: 05.03.2010
Сообщений: 1,256
04.04.2010, 11:50     Рекурсия: составить цепочку максимальной длины по правилам игры "Города" #5
если умеешь считывать из файла, то делаешь это и записываешь всю информацию в массив типа char, далее ищешь в массиве знак разделителя слов, т.е. если слова через запятую записаны, то ищешь запятую, если каждое слово начинается с новой строки, то ищешь \n и пока не встретится такой символ, переписываешь слова в двумерный массив
ну и далее ф-ция strlen() определяет длину строки и с ее помощью не трудно узнать, какая по счету последняя буква слова(данной строки)
потом ищешь в каждой строке или первый элемент совпадает с нашей буквой и выводишь это слово
поменять слово(строку), с другой можно с помощью ф-ции swap() или вручную
DmitrijN
0 / 0 / 0
Регистрация: 01.04.2010
Сообщений: 9
04.04.2010, 12:13     Рекурсия: составить цепочку максимальной длины по правилам игры "Города" #6
Цитата Сообщение от Vorona Посмотреть сообщение
если умеешь считывать из файла, то делаешь это и записываешь всю информацию в массив типа char, далее ищешь в массиве знак разделителя слов

strtok() поможет тебе это сделать.

C
1
2
3
char s[]="Hello, world!";
strtok(s, ",");
printf("row is: %s", s);
На экран ты должен получить, что-то вроде Hello
Vorona
Peace 2 all shining faces
 Аватар для Vorona
660 / 522 / 44
Регистрация: 05.03.2010
Сообщений: 1,256
04.04.2010, 12:24     Рекурсия: составить цепочку максимальной длины по правилам игры "Города" #7
DmitrijN, да, только у нас много слов и придется запоминать номер элемента массива, который равен ',' к примеру, и от этого элемента+1 придется все время отталкиваться
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.04.2010, 12:44     Рекурсия: составить цепочку максимальной длины по правилам игры "Города"
Еще ссылки по теме:

C++ Найти в функции в строке слово максимальной длины
Вывод двух слов максимальной длины C++
C++ Подсветить предложение максимальной длины

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

Или воспользуйтесь поиском по форуму:
art_stalker
0 / 0 / 0
Регистрация: 02.04.2010
Сообщений: 8
04.04.2010, 12:44  [ТС]     Рекурсия: составить цепочку максимальной длины по правилам игры "Города" #8
Как мне приспособить код который во 2-ом посте чтобы он работал не с буквами, а со словами?
Идея у меня такая: я из кода в котором получу все перестановки слов запишу их в текстовый файл, потом открою его и начну искать все 1-вые и последние буквы в каждой строчке, где у меня совпадет последняя и первая буква ту строку и выведу на вывод.

Вот примерный код нахождения букв (какой смог написать):
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
#include<stdio.h>
#include<string.h>
#include<conio.h>
#define YES 1
#define NO 0
 
 
void main()
{
    //FILE *in;
    int n,i,j,beg;
    const int m=10;
    char *string[m],d;
    //in=fopen("goroda.txt","r");
    int inword=NO;
    i=0;
    while(gets(string[i])!=NULL)
    i++;
    int k=i;
    printf("\n");
    for(i=0;i<k;i++)
    {
        n=strlen(string[i]);
        for(j=0;j<=n;j++)
        if(*(string[i]+j)==',')
        {
            if(inword==YES)
            {
                d=*(string[i]+j-1);
                a=*(string[i]+beg);
            }
            inword=NO;
        }
        else
            if(inword==NO)
            {
                inword=YES;
                beg=j;
            }
    }
    for(i=0;i<k;i++)
        puts(string[i]);
    getch();
    printf("\n");
}
Yandex
Объявления
04.04.2010, 12:44     Рекурсия: составить цепочку максимальной длины по правилам игры "Города"
Ответ Создать тему
Опции темы

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