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

По строкам s2 и s3 восстановить строку s1 - C++

Восстановить пароль Регистрация
 
Kappa
0 / 0 / 0
Регистрация: 23.06.2014
Сообщений: 21
23.06.2014, 18:24     По строкам s2 и s3 восстановить строку s1 #1
Заданная строка s1. После удаления одной буквы с s1 образуется строку s2. После удаления из s1 другой буквы образуется строка s3. по строкам s2 и s3 восстановить строку s1.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.06.2014, 18:24     По строкам s2 и s3 восстановить строку s1
Посмотрите здесь:

Задача по строкам в С C++
Задание по строкам! C++
C++ Задача по строкам
C++ по строкам
C++ Задача по строкам
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
skaa
Хочу в Исландию
 Аватар для skaa
1024 / 823 / 75
Регистрация: 10.11.2010
Сообщений: 1,626
23.06.2014, 20:32     По строкам s2 и s3 восстановить строку s1 #2
qcs - длина строки s1
s4 - строка с результатом
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
    s4[qcs]='\0';
    for(nc=0;nc<qcs;nc++)
    {
        if(s2[nc]!=s3[nc])
            break;
        s4[nc]=s2[nc];
    }
    for(nc2=qcs-2;nc2>=0;nc2--)
    {
        if(s2[nc2]!=s3[nc2])
            break;
        s4[1+nc2]=s2[nc2];
    }
 
    if(strncmp(s2+nc+1,s3+nc,nc2-nc-1)==0)
    {
        s4[nc++]=s2[nc];
        for(;nc<=nc2+1;nc++)
            s4[nc]=s3[nc-1];
    }
    else
    {
        s4[nc++]=s3[nc];
        for(;nc<=nc2+1;nc++)
            s4[nc]=s2[nc-1];
    }
Kappa
0 / 0 / 0
Регистрация: 23.06.2014
Сообщений: 21
24.06.2014, 00:26  [ТС]     По строкам s2 и s3 восстановить строку s1 #3
skaa, Спасибо,а можно задачу полную, строки не совсем понимаю,хочу посмотреть с самого начала .
skaa
Хочу в Исландию
 Аватар для skaa
1024 / 823 / 75
Регистрация: 10.11.2010
Сообщений: 1,626
24.06.2014, 01:20     По строкам s2 и s3 восстановить строку s1 #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
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
70
71
72
73
74
75
76
void    main()
{
    int qcs=10;
    char    *s1,*s2,*s3,*s4;
    int nc,nc2;
    int jc;
    time_t  rt;
    char    cj;
 
    time(&rt);
    for(nc=rt%qcs-1;nc>=0;nc--)
        rand();
 
    s1=new char[qcs+1];
    s2=new char[qcs];
    s3=new char[qcs];
    s4=new char[qcs+1];
 
    for(jc=0;jc<qcs;jc++)
    {
        cj='A'+(1.*rand()/RAND_MAX)*26;
        s1[jc]=cj;
    }
    s1[jc]='\0';
 
    nc=(1.*rand()/RAND_MAX)*qcs;
    for(;;)
    {
        nc2=(1.*rand()/RAND_MAX)*qcs;
        if(nc2!=nc)
            break;
    }
    nc=9;nc2=2;
 
    for(jc=0;jc<nc;jc++)s2[jc]=s1[jc];
    for(jc=nc;jc<qcs-1;jc++)s2[jc]=s1[1+jc];
    s2[jc]='\0';
    for(jc=0;jc<nc2;jc++)s3[jc]=s1[jc];
    for(jc=nc2;jc<qcs-1;jc++)s3[jc]=s1[1+jc];
    s3[jc]='\0';
 
    s4[qcs]='\0';
    for(nc=0;nc<qcs;nc++)
    {
        if(s2[nc]!=s3[nc])
            break;
        s4[nc]=s2[nc];
    }
    for(nc2=qcs-2;nc2>=0;nc2--)
    {
        if(s2[nc2]!=s3[nc2])
            break;
        s4[1+nc2]=s2[nc2];
    }
 
    if(strncmp(s2+nc+1,s3+nc,nc2-nc-1)==0)
    {
        s4[nc++]=s2[nc];
        for(;nc<=nc2+1;nc++)
            s4[nc]=s3[nc-1];
    }
    else
    {
        s4[nc++]=s3[nc];
        for(;nc<=nc2+1;nc++)
            s4[nc]=s2[nc-1];
    }
 
    if(strcmp(s1,s4)!=0)
        nc2=nc;
 
    delete[] s1;
    delete[] s2;
    delete[] s3;
    delete[] s4;
}
Kappa
0 / 0 / 0
Регистрация: 23.06.2014
Сообщений: 21
24.06.2014, 10:40  [ТС]     По строкам s2 и s3 восстановить строку s1 #5
skaa, Спасибо большое ,работает .Но я сам не до конца понял как оно работает. Можете обьяснить или дать какой-нибудь контакт(скайп,е-пошта и тд.),хотелось бы понять как это делать .
skaa
Хочу в Исландию
 Аватар для skaa
1024 / 823 / 75
Регистрация: 10.11.2010
Сообщений: 1,626
24.06.2014, 17:23     По строкам s2 и s3 восстановить строку s1 #6
Попробуйте сделать эту задачу вручную. Если останутся вопросы, тогда будем думать дальше .
Mr.X
Эксперт С++
 Аватар для Mr.X
2804 / 1580 / 248
Регистрация: 03.05.2010
Сообщений: 3,683
24.06.2014, 23:02     По строкам s2 и s3 восстановить строку s1 #7
Если возможны варианты ответа, то программа находит их все:
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/////////////////////////////////////////////////////////////////////////////////////////
//Заданная строка s1. После удаления одной буквы с s1 образуется строку s2. После удаления 
//из s1 другой буквы образуется строка s3. по строкам s2 и s3 восстановить строку s1.
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <iterator>
#include <set>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string         T_str;
typedef std::set< T_str >   T_strings;
/////////////////////////////////////////////////////////////////////////////////////////
T_strings  get_restored_strings
    (
        T_str   const   &   AA,
        T_str   const   &   BB
    )
{
    T_strings   res_strings;
 
    if  (
            AA.size() == BB.size()
        )
    {
        for( size_t   max_pref_size = 0; max_pref_size < AA.size(); ++max_pref_size )
        {
            T_str   A   =   AA;
            T_str   B   =   BB;
 
            T_str   pref;
 
            while   (
                            A.size()    >   1
                        &&  A.front()   ==  B.front()
                        &&  pref.size() <   max_pref_size
                    )
            {
                pref    +=  A.front();
                A.erase( 0, 1 );
                B.erase( 0, 1 );
            }
 
            T_str   suff;
 
            while   (
                            A.size()    >   1
                        &&  A.back()    ==  B.back()
                    )
            {
                suff    +=  A.back();
                A.pop_back();
                B.pop_back();
            }
            std::reverse
                (
                    suff.begin  (),
                    suff.end    ()
                );
 
            for( int  i = 0; i < 2; ++i )
            {
                if  (
                            B.front()    +   A
                        ==  B            +   A.back()
                    )
                {
                    res_strings.insert
                        (
                                pref
                            +   B.front()    +   A
                            +   suff
                        );
                }//if
 
                std::swap( A, B );
            }//for
        }//for
    }//if
 
    return  res_strings;
}
/////////////////////////////////////////////////////////////////////////////////////////
void  print_strings( T_strings  const   &   strings )
{
    if( strings.empty() )
    {
        std::cout   <<  "Нет ответа.";
    }
 
    std::copy
        (
            strings.begin   (),
            strings.end     (),
            std::ostream_iterator<T_str>( std::cout, "\n" )
        );
}
/////////////////////////////////////////////////////////////////////////////////////////
int  main()
{
    std::locale::global(std::locale(""));
 
    for(;;)
    {
        T_str   A;
        std::cout   <<  "\n\n\n\n\nподстрока 1: ";
        std::cin    >>  A;
 
        T_str   B;
        std::cout   <<  "подстрока 2: ";
        std::cin    >>  B;
 
        T_strings   strings     =   get_restored_strings( A, B );
 
        print_strings( strings );
    }//for
}
Qwertiy
817 / 625 / 75
Регистрация: 20.08.2013
Сообщений: 2,525
25.06.2014, 00:29     По строкам s2 и s3 восстановить строку s1 #8
Цитата Сообщение от Mr.X Посмотреть сообщение
Если возможны варианты ответа, то программа находит их все:
Не думаю. Что будет, если строки AA и BB одинаковы?
IrineK
Заблокирован
25.06.2014, 01:10     По строкам s2 и s3 восстановить строку s1 #9
Ответа не будет, если остатки одинаковы.
Если в остатке - разница в два символа, то будет два варианта ответа.
Однозначного ответа как-то не видится.
Qwertiy
817 / 625 / 75
Регистрация: 20.08.2013
Сообщений: 2,525
25.06.2014, 03:07     По строкам s2 и s3 восстановить строку s1 #10
Цитата Сообщение от IrineK Посмотреть сообщение
Ответа не будет, если остатки одинаковы.
Неверно. Например, если исходная строка состояла из n повторов одного символа, то ответ однозначен. В общем случае, если остатки одинаковые, можно удвоить любой символ, т. е. при одном удалении вычёркивалось его первое вхождение, а при другом - второе.

Добавлено через 3 минуты
Цитата Сообщение от IrineK Посмотреть сообщение
Однозначного ответа как-то не видится.
Да почти везде.
123567890
123456890
(123) [567 # 456] (890) => (123) (4567) (890)
IrineK
Заблокирован
25.06.2014, 04:35     По строкам s2 и s3 восстановить строку s1 #11
Цитата Сообщение от Qwertiy Посмотреть сообщение
если исходная строка состояла из n повторов одного символа
Игра в том, что мы не знаем, что было на входе.

Добавлено через 6 минут
Уточню про два варианта: если потеряны соседние символы, то восстановить однозначно нельзя.
Mr.X
Эксперт С++
 Аватар для Mr.X
2804 / 1580 / 248
Регистрация: 03.05.2010
Сообщений: 3,683
25.06.2014, 07:58     По строкам s2 и s3 восстановить строку s1 #12
Цитата Сообщение от Qwertiy Посмотреть сообщение
Не думаю. Что будет, если строки AA и BB одинаковы?
А чего тут думать, прыгать надо, то бишь запускать мою программу:
Миниатюры
По строкам s2 и s3 восстановить строку s1  
IrineK
Заблокирован
25.06.2014, 10:00     По строкам s2 и s3 восстановить строку s1 #13
Mr.X,
допёрла. По условию то удаляются символы обязательно на разных позициях.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.06.2014, 10:27     По строкам s2 и s3 восстановить строку s1
Еще ссылки по теме:

переделать программу Pascal -> C++ (Восстановить исходную матрицу и напечатать ее по строкам) C++
Программа по строкам C++
C++ Задача по строкам

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

Или воспользуйтесь поиском по форуму:
Qwertiy
817 / 625 / 75
Регистрация: 20.08.2013
Сообщений: 2,525
25.06.2014, 10:27     По строкам s2 и s3 восстановить строку s1 #14
Цитата Сообщение от Mr.X Посмотреть сообщение
А чего тут думать, прыгать надо, то бишь запускать мою программу
Хм.. Кажется, цикл не заметил.
Yandex
Объявления
25.06.2014, 10:27     По строкам s2 и s3 восстановить строку s1
Ответ Создать тему
Опции темы

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