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

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

Войти
Регистрация
Восстановить пароль
 
SpblrT
1 / 1 / 0
Регистрация: 24.11.2011
Сообщений: 40
#1

символьные строки А и Б - C++

29.12.2011, 15:36. Просмотров 673. Ответов 11
Метки нет (Все метки)

заданы 2 символьные строки А и Б . Требуется вычислить сколькими способами можно получить строку В из строки А, вычеркивая некоторые символы, например для строк aaabbbccc и abc это число равно 36

напишите пожалуйста код задачи, или пример хотябы..
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.12.2011, 15:36     символьные строки А и Б
Посмотрите здесь:

символьные строки - C++
Преобразовать строку таким образом, чтобы в ее начале были записаны слова, содержащие только цифры, потом слова, содержащие только...

Символьные строки - C++
Задача такая: надо отделить имя файла и расширение от его пути но из за слэшей на экран выводится какаята ерунда, никак непохожая на...

Символьные строки - C++
Ввести с экрана строку. В строке подсчитать количество запятых и точек. Вывести на экран исходную строку и количество запятых и точек в ней...

Символьные строки - C++
Я, конечно, туп, но как взять половину первой строки при соединение строк? (задание: Ввести с клавиатуры строку. Определить во введенных...

символьные строки - C++
как инициализировать символьную строку так, чтобы туда засунуть русские буквы? так чтобы не белеберда была

Символьные строки и функции - C++
Создайте функцию, которая печатает строку и сообщает количество напечатанных символов.

Символьные строки и функции - C++
Приветик всем, Я не могу понять, что от меня требуется: Разработать функцию. Функция - Left(s,l). Назначение - выравнивание строки s...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
asm
62 / 35 / 1
Регистрация: 05.10.2011
Сообщений: 137
29.12.2011, 15:58     символьные строки А и Б #2
А как получилось 36?
Для "aaabbbccc" и "abc" вроде должно получиться 27=3*3*3.
SpblrT
1 / 1 / 0
Регистрация: 24.11.2011
Сообщений: 40
29.12.2011, 22:22  [ТС]     символьные строки А и Б #3
не знаю( мне такое условие дали..
по моему это типа 36 раз aaabbbccc можно по разному записать типа bbbcccaaa, abcabcabc, aacbbaccb .... и т.д. я так понял
BRcr
4006 / 2295 / 155
Регистрация: 03.02.2011
Сообщений: 5,064
Записей в блоге: 10
29.12.2011, 22:27     символьные строки А и Б #4
Цитата Сообщение от SpblrT Посмотреть сообщение
по моему это типа 36 раз aaabbbccc можно по разному записать типа bbbcccaaa, abcabcabc, aacbbaccb .... и т.д. я так понял
неа, опять мимо тогда получится 9*9*9 = 729 комбинаций.
Thinker
Эксперт C++
4221 / 2195 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
29.12.2011, 22:29     символьные строки А и Б #5
SpblrT, таких комбинаций ровно http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{9!}{(3!)^3} = 1680, что-то вы очень не то говорите
BRcr
4006 / 2295 / 155
Регистрация: 03.02.2011
Сообщений: 5,064
Записей в блоге: 10
29.12.2011, 22:35     символьные строки А и Б #6
Thinker, почему???
девять позиций, каждая может иметь одно из трех независимых состояний - итого девять в кубе вариаций... разве нет?
Thinker
Эксперт C++
4221 / 2195 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
29.12.2011, 22:36     символьные строки А и Б #7
BRcr, перестановки с повторениями элементов:
http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{(n_1+...+n_k)!}{n_1!...n_k!}
BRcr
4006 / 2295 / 155
Регистрация: 03.02.2011
Сообщений: 5,064
Записей в блоге: 10
29.12.2011, 23:31     символьные строки А и Б #8
Thinker, никак не могу согласиться; формулы - это хорошо, конечно, но логика - лучше.
Подумавши маленько.... итого: в троичной системе исчисления, однозначное значение даст нам три уникальных комбинации, двухзначное даст три комбинации трижды, в сумме девять, трехзначное - девять комбинаций трижды и тд.
Вполне очевидно, количество вариантов будет равно основе системы счисления, возведенной в степень, равную количеству знаков числа. Стало быть, в данном случае это 3^9 = 19683.
asm
62 / 35 / 1
Регистрация: 05.10.2011
Сообщений: 137
30.12.2011, 03:50     символьные строки А и Б #9
Цитата Сообщение от SpblrT Посмотреть сообщение
...вычеркивая некоторые символы...
вообще-то если вычеркивать, то получается как раз 27 комбинаций

Добавлено через 3 часа 16 минут
Вот что у меня получилось:
С++ код

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
118
119
//---------------------------------------------------------------------------
#include <windows.h>
#include <iostream.h>
 
#pragma hdrstop
 
//---------------------------------------------------------------------------
char* Rus(const char*);
bool existTest(string A, string B);
bool lastTest(bool *M, unsigned int A, unsigned int B);
void verify(bool *q, string C, string B, unsigned int *c);
 
#pragma argsused
int main(int argc, char* argv[])
{
        string A,B,C,D,E;
        A = " bb cc bb cc ";
        B = "bc";
        unsigned int b=0,c=0;
 
        bool *q ;
 
        for(unsigned int i=0;i<A.length();i++)
        for(unsigned int j=0;j<B.length();j++)
        {
                if(A[i]==B[j])
                {
                        C.push_back(A[i]);
                        break;
                }
        }
 
        if(!existTest(C,B))
        {
                cout<<Rus("Решений не найдено")<<endl;
                goto END;
        }
 
        q = new bool[C.length()];
        for(unsigned int i=0;i<B.length();i++) q[i]=true;
        for(unsigned int i=B.length();i<C.length();i++) q[i]=false;
            //
            verify(q,C,B,&c);
            //
        while( !lastTest(q,C.length(),B.length()) )
        {
 
                for(unsigned int i=B.length()-1+b;i<C.length()-1;i++)
                {
                        bool temp = q[i];
                        q[i] = q[i+1];
                        q[i+1] = temp;
                        //
                        verify(q,C,B,&c);
                        //
                }
                        q[B.length()-1+b] = true;
                        q[C.length()-1] = false;
 
                q[b]=false;
                q[b+B.length()]=true;
                //
                verify(q,C,B,&c);
                //
                b++;
        }
 
 
 
 
        cout<<"A="<<A<<endl;
        cout<<"B="<<B<<endl;
        cout<<"C="<<C<<endl;
        cout<<"c="<<c<<endl;
END:
 
        system("PAUSE");
        return 0;
}
//---------------------------------------------------------------------------
char bufRus[256];
char* Rus(const char*text)
{
        CharToOemA(text,bufRus);
        return bufRus;
}
//---------------------------------------------------------------------------
bool existTest(string A, string B)
{
        unsigned int a=0;
        for(unsigned int i=0,j=0;i<B.length();i++)
                while(j<A.length())
                {
                        if(B[i]==A[j++])
                        {
                                a++;
                                break;
                        }
                }
        if(a<B.length()) return false;
        return true;
}
//---------------------------------------------------------------------------
bool lastTest(bool *M, unsigned int A, unsigned int B)
{
        for(unsigned int i=A-1;i>A-B-1;i--)
        if(!M[i])return false;
        return true;
}
//---------------------------------------------------------------------------
void verify(bool *q, string C, string B, unsigned int *c)
{
        string temp;
        for(unsigned int i=0; i<C.length(); i++)
                if(q[i])temp.push_back(C[i]);
        if(existTest(temp,B))
                *c=*c + 1;
}
//---------------------------------------------------------------------------


Долго думал как сделать, так толком ничего и не придумал, а программа работает с горем пополам. То есть что-то считает, но далеко не все комбинации проходят. Может тут надо было рекурсию использовать каким-нибудь боком? Не знаю. В общем я написал и выглядит громоздко. Хорошая задача, да вот сложная.
SpblrT
1 / 1 / 0
Регистрация: 24.11.2011
Сообщений: 40
30.12.2011, 14:06  [ТС]     символьные строки А и Б #10
спасибо
alkagolik
Заблокирован
30.12.2011, 16:23     символьные строки А и Б #11
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
 
void selectSort( char* arr, int size )
{
    int tmp, i, j, pos;
    for( i = 0; i < size; ++i ) // i - номер текущего шага
    {
        pos = i;
        tmp = arr[ i ];
        for( j = i + 1; j < size; ++j ) // цикл выбора наименьшего элемента
        {
            if ( arr[ j ] < tmp )
            {
               pos = j;
               tmp = arr[ j ];
            }
        }
        arr[ pos ] = arr[ i ];
        arr[ i ] = tmp; // меняем местами наименьший с a[i]
    }
}
 
uint64_t mypow ( uint64_t base, uint64_t power ) {
 
    uint64_t tmp = base;
 
    while ( power-- > 1 )
        tmp *= base;
    return tmp;
}
 
int main (void)
{
    char src[] = "abcabcabc";
    char wrd[] = "abac";
    char ch, *tmp;
    char *p = &wrd[ 0 ], *beg = &wrd[ 0 ];
    uint64_t power, base = 0, res = 1;
    uint8_t flag = 1;
 
    selectSort( src, strlen( src ) );
    selectSort( wrd, strlen( wrd ) );
 
    while ( *p ) {
 
        base = 0;
        ch = *p;
 
        while ( *p == *beg && *beg )
            ++beg;
        power = beg - p;
        p = beg;
 
        if ( (tmp = strchr( src, ch ) ) == NULL ) {
            puts("0 способов");
            flag = 0;
            break;
        }
        else
            while ( *tmp++ == ch )
                ++base;
 
        res *= mypow( base, power );
    }
 
    if ( flag )
        printf( "%llu способов", res );
    return 0;
}
Добавлено через 12 минут
сколькими способами можно составить слово "ааа" из входного множества "а"? http://www.cyberforum.ru/cgi-bin/latex.cgi?1^{3}= 1 А если входное множество "аа"? тогда http://www.cyberforum.ru/cgi-bin/latex.cgi?2 ^{3} = 8 То же проделываем с каждым из символов попутно домножая результат.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.12.2011, 19:24     символьные строки А и Б
Еще ссылки по теме:

Символьные и переменные строки - C++
Вывести на экран монитора строковый треугольник: ABC……………….……….....………..Z BC…………………………………Z C……………………………..Z ………….. Z

Символьные строки и функции - C++
Помогите написать функцию Right(s,l) для выравнивание строки s по правому краю до длины l.

Даны две символьные строки А и В - C++
Даны две символьные строки А и В. Составьте программу, проверяющую, можно ли из букв, входящих в А, составить В. буквы можно переставлять и...

Указатели, символьные строки и функции - C++
Функция разбивает строку на две части: до первого вхождения за-данного символа и после него. буду очень солидарен.

Символьные строки. Разделение на слова - C++
Помогите написать прогу. Не могу разобраться, какие команды применить. Так же нужно использовать отдельно функцию. В Файле находится...


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

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
4221 / 2195 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
30.12.2011, 19:24     символьные строки А и Б #12
Цитата Сообщение от BRcr Посмотреть сообщение
Thinker, никак не могу согласиться; формулы - это хорошо, конечно, но логика - лучше.

Не по теме:

почитайте о перестановках с повторениями и посмотрите примеры. Вы правильно говорите, логика это хорошо, она то и помогает выводить и доказывать формулы, а также правильно их применять))

Yandex
Объявления
30.12.2011, 19:24     символьные строки А и Б
Ответ Создать тему
Опции темы

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