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

Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.92
SpblrT
1 / 1 / 0
Регистрация: 24.11.2011
Сообщений: 40
20.12.2011, 20:06     Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы #1
)заданы 2 символьные строки А и Б . Требуется вычислить сколькими способами можно получить строку В из строки А, вычеркивая некоторые символы, например для строк aaabbbccc и abc это число равно 36

хотябы 1 стособ

 Комментарий модератора 
Создавайте темы с осмысленными и понятными названиями - это серьезно повышает шансы, что на ваш вопрос ответят.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.12.2011, 20:06     Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы
Посмотрите здесь:

Вывести текст файла, заменив цифры от 0 до 9 на слова "ноль", "один"."девять", начиная каждое предложение с новой строки C++
C++ Определить число вхождений в строку подстроки "аба", вывести символы строки, не являющейся буквами или цифрами
C++ Необработанное исключение в "0x013f2b22" в "123.exe": 0xC0000005: Нарушение прав доступа при записи "0xfdfdfdfd"
Как использовать символы из русского алфавита, а так же символы типа "█" "░" и т.д.? C++
C++ разработать программу для работы со строками: найти и заменить в ней все символы "а" на "b"
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.12.2011, 05:33     Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы #2
Какие ограничения на длины строк и на время выполнения программы?
challengerr
42 / 35 / 2
Регистрация: 30.07.2008
Сообщений: 136
21.12.2011, 09:03     Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы #3
например для строк aaabbbccc и abc это число равно 36
Не может ли кто-нибудь объяснить, почему количество способов 36? (если оно действительно 36)
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.12.2011, 09:09     Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы #4
Цитата Сообщение от challengerr Посмотреть сообщение
Не может ли кто-нибудь объяснить, почему количество способов 36? (если оно действительно 36)
для данного случая кол-во способов: 3^3=36
challengerr
42 / 35 / 2
Регистрация: 30.07.2008
Сообщений: 136
21.12.2011, 09:16     Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы #5
для данного случая кол-во способов: 3^3=36
3^3 = 27 (3*3*3 = 27)
У меня получается 90 способов при ручном построении дерева
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.12.2011, 09:28     Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы #6
Цитата Сообщение от challengerr Посмотреть сообщение
3^3 = 27 (3*3*3 = 27)
насчет 3^3=36 я погорячился, правильный ответ будет 27:
aaa - можно выбрать a тремя вариантами.
aaabbb - можно выбрать ab - 3*3 вариантами
aaabbbccc - можно выбрать abc - 3*3*3 вариантами
а Вы покажите свой способ на 90 вариантов
challengerr
42 / 35 / 2
Регистрация: 30.07.2008
Сообщений: 136
21.12.2011, 09:32     Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы #7
Где я ошибся в логике?
Начальная строка (aaabbbccc)
Три варианта вычеркивания с получением следующих строк:
(aabbbccc)=k1 и (aaabbccc)=k2 и (aaabbbcc)=k3
Из строки (aabbbccc)=k1 вычеркиванием можно получить:
(abbbccc)=k11 и (aabbccc)=k12 и (aabbbcc)=k13
Из строк k2, k3 эквивалентно k1
Из строки (abbbccc)=k11 вычеркиванием получают:
(abbccc)=k111 и (abbbcc)=k112
Из строки (abbccc)=k111 вычеркиванием получают:
(abccc) и (abbcc)
(abccc) - 1 способ получить (abc)
(abbcc) - 2 способа получить (abc)
Из строки (abbbcc)=k112 вычеркиванием получают:
(abbcc) и (abbbc)
(abbcc) - 2 способа получить (abc)
(abbbc) - 1 способ получить (abc)
Итого: 6 способов для k11

Из строки (aabbccc)=k12 вычеркиванием получают:
(abbccc)=k121 и (aabccc)=k122 и (aabbcc)=k123
Из строки (abbccc)=k121 вычеркиванием получают:
(abccc)=k1211 и (abbcc)=k1212
(abccc) - 1 способ получить (abc)
(abbcc) - 2 способа получить (abc)
Из строки (aabccc)=k122 вычеркиванием получают:
(abccc)=k1221 и (aabcc)=k1222
(abccc) - 1 способ получить (abc)
(aabcc) - 2 способа получить (abc)
Из строки (aabbcc)=k123 вычеркиванием получают:
(abbcc)=k1231 и (aabcc)=k1232 и (aabbc)=k1233
(abbcc) - 2 способа получить (abc)
(aabcc) - 2 способа получить (abc)
(aabbc) - 2 способа получить (abc)
Итого: 12 способов для k12
Итого: 12 способов для k13
Итого для k11 и для k12 и для k13 12+12+6 = 30 способов для k1
Аналогично 30 способов для k2
Аналогично 30 способов для k3
де ошибся в рассуждениях, если 36?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.12.2011, 09:41     Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы #8
Цитата Сообщение от challengerr Посмотреть сообщение
Начальная строка (aaabbbccc)
Три варианта вычеркивания с получением следующих строк:
(aabbbccc)=k1 и (aaabbccc)=k2 и (aaabbbcc)=k3
Не три варианта. Например вариант (aabbbccc)=k1 можно получить не одним способом а тремя:
- первый вариант - вычеркнуть первую букву a
- второй вариант - вычеркнуть вторую букву a
- третий вариант - вычеркнуть третью букву a
Вы ошибаетесь вот в чем:
Например есть строка: abcxy
Нужно получить строку: abc
Здесь один вариант: вычеркнуть x и y
А у Вас будет получаться два варианта:
- первый вариант - вычеркнуть сначало x, потом вычекнуть y
- второй вариант - вычеркнуть сначало y, потом вычеркнуть x
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
21.12.2011, 09:45     Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы #9
Простой алгоритм - можно подсчитать количество каждой буквы из строки Б в строке А. Потом так же перемножить как в случае с aaabbbccc и abc, где умножается 3 ( количество букв а ) на 3 ( количество букв b ) и еще раз на 3 ( количество букв c ).
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.12.2011, 09:47     Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы #10
Цитата Сообщение от Toshkarik Посмотреть сообщение
Простой алгоритм - подсчитать количество каждой буквы из строки Б в строке А. Потом так же перемножить как в случае с aaabbbccc и abc, где умножается 3 ( количество букв а ) на 3 ( количество букв b ) и еще раз на 3 ( количество букв c ).
такой алгоритм не подойдет к варианту:
aabbccabc <- первая строка
abc <- вторая строка
challengerr
42 / 35 / 2
Регистрация: 30.07.2008
Сообщений: 136
21.12.2011, 09:52     Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы #11
У меня были варианты вычеркивания без учета расположения элементов.
Вы написали варианты с учетом расположения элементов.
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
21.12.2011, 09:52     Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы #12
valeriikozlov, Почему же? Все вполне так же, 27 вариантов. Или я не допонял задание? Нельзя подразумевать перестановку?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.12.2011, 10:00     Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы #13
Цитата Сообщение от Toshkarik Посмотреть сообщение
Все вполне так же, 27 вариантов
Вручную покажете, как из строки:
aabbccabc
получить строку:
abc
не переставляя буквы, а только их вычеркивая?
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
21.12.2011, 10:07     Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы #14
Так я же и спросил про перестановку, про нее в задании ничего не сказано, тогда почему нельзя ее делать?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.12.2011, 10:20     Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы #15
Цитата Сообщение от Toshkarik Посмотреть сообщение
Так я же и спросил про перестановку, про нее в задании ничего не сказано, тогда почему нельзя ее делать?
ну вроде как в задании сказано только про вычеркивание.

Добавлено через 9 минут
Цитата Сообщение от challengerr Посмотреть сообщение
У меня были варианты вычеркивания без учета расположения элементов.
Вы написали варианты с учетом расположения элементов.
У меня вариант естественно с учетом расположения элементов (потому что в задании сказано только про вычеркивание).
Ваш вариант тоже кстати учитывает расположение элементов, но еще он учитывает порядок вычеркивания (а мой вариант учитывает какие именно элементы были вычеркнуты).
Я не говорю что Ваш вариант не правильный, оба варианты правильные - просто для разных случаев подсчета.
В условии задачи есть недосказанность:
Например для Вашего варианта можно было бы написать так:
Различный порядок вычеркивания одних и тех же элементов - является разными вариантами.
А для моего варианта можно было бы написать:
Вычеркивание одних и тех же букв находящихся на различных местах является разными вариантами.
Не исключаю, что имеется еще какой-то вариант учета вычеркиваний, который даст результат именно 36.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.12.2011, 10:26     Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы
Еще ссылки по теме:

Вывести сообщение "Можно", если из букв введенной строки X можно составить введенную строку Y C++
C++ Ввести 2 строки и вывести на экран "Можно" если из 1 строки можно составить 2 строку
Из слова "яблоко" путем склеек и вырезок его букв получить слова "блок" и "око" C++

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

Или воспользуйтесь поиском по форуму:
challengerr
42 / 35 / 2
Регистрация: 30.07.2008
Сообщений: 136
21.12.2011, 10:26     Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы #16
Дано:
А = {a1,a2,a3,...,an}
B = {b1,b2,b3,...,bm}
(m > n) => (решений нет)
(m = n) и (A<>B) => (решений нет)
(m = n) и (A=B) => ()
(m < n)
(Когда элемент можно вычеркнуть?)
{b1,b2,b3,...,bm} сохраняется в {a1,a2,a3,...ak-1, ak+1,...,an} => элемент ak из {a1,a2,a3,...ak-1, ak, ak+1,...,an} можно вычеркнуть
(Какие элементы можно вычеркнуть на первом шаге?)
Вычеркиваем элементы a1,...,an из А по порядку и проверяем сохранилась ли B в А
Получаем последовательность A2. Повторяем процедуру.
При Ab = B засчитываем способ. Предлагаю такой алгоритм.
Yandex
Объявления
21.12.2011, 10:26     Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы
Ответ Создать тему
Опции темы

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