Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.92
SpblrT
1 / 1 / 1
Регистрация: 24.11.2011
Сообщений: 40
#1

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

20.12.2011, 20:06. Просмотров 1736. Ответов 15
Метки нет (Все метки)

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

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

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

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно"
В зависимости от времени года "весна", "лето", "осень", "зима" определить...

Для каждой строки найти слова, которые не имеют ни одного из букв: "l", "k", "r", "s" i "j"
Задано символьные строки. Строка состоит из нескольких слов (наборов символов),...

Из данной строки сделать новую строку, заменив в ней все слова: "один", "два", "три" и т.д на соответствующие цифры
Из данной строки сделать новую строку, заменив в ней все слова: "один", "два",...

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование)
Разработать программу с использованием наследования классов, реализующую...

После каждого знака препинания (".", ",", ";") вставить в строку пробел, если там его нет
Выполните задания с использованием библиотечного класса string. Даны строка...

Вывести текст файла, заменив цифры от 0 до 9 на слова "ноль", "один"."девять", начиная каждое предложение с новой строки
Написать программу, которая считывает текст из файла и выводит его на экран,...

15
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
21.12.2011, 05:33 #2
Какие ограничения на длины строк и на время выполнения программы?
0
challengerr
43 / 36 / 6
Регистрация: 30.07.2008
Сообщений: 136
21.12.2011, 09:03 #3
например для строк aaabbbccc и abc это число равно 36
Не может ли кто-нибудь объяснить, почему количество способов 36? (если оно действительно 36)
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
21.12.2011, 09:09 #4
Цитата Сообщение от challengerr Посмотреть сообщение
Не может ли кто-нибудь объяснить, почему количество способов 36? (если оно действительно 36)
для данного случая кол-во способов: 3^3=36
0
challengerr
43 / 36 / 6
Регистрация: 30.07.2008
Сообщений: 136
21.12.2011, 09:16 #5
для данного случая кол-во способов: 3^3=36
3^3 = 27 (3*3*3 = 27)
У меня получается 90 способов при ручном построении дерева
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 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 вариантов
0
challengerr
43 / 36 / 6
Регистрация: 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?
1
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 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
0
Toshkarik
1149 / 866 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 1
21.12.2011, 09:45 #9
Простой алгоритм - можно подсчитать количество каждой буквы из строки Б в строке А. Потом так же перемножить как в случае с aaabbbccc и abc, где умножается 3 ( количество букв а ) на 3 ( количество букв b ) и еще раз на 3 ( количество букв c ).
1
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
21.12.2011, 09:47 #10
Цитата Сообщение от Toshkarik Посмотреть сообщение
Простой алгоритм - подсчитать количество каждой буквы из строки Б в строке А. Потом так же перемножить как в случае с aaabbbccc и abc, где умножается 3 ( количество букв а ) на 3 ( количество букв b ) и еще раз на 3 ( количество букв c ).
такой алгоритм не подойдет к варианту:
aabbccabc <- первая строка
abc <- вторая строка
1
challengerr
43 / 36 / 6
Регистрация: 30.07.2008
Сообщений: 136
21.12.2011, 09:52 #11
У меня были варианты вычеркивания без учета расположения элементов.
Вы написали варианты с учетом расположения элементов.
0
Toshkarik
1149 / 866 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 1
21.12.2011, 09:52 #12
valeriikozlov, Почему же? Все вполне так же, 27 вариантов. Или я не допонял задание? Нельзя подразумевать перестановку?
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
21.12.2011, 10:00 #13
Цитата Сообщение от Toshkarik Посмотреть сообщение
Все вполне так же, 27 вариантов
Вручную покажете, как из строки:
aabbccabc
получить строку:
abc
не переставляя буквы, а только их вычеркивая?
0
Toshkarik
1149 / 866 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 1
21.12.2011, 10:07 #14
Так я же и спросил про перестановку, про нее в задании ничего не сказано, тогда почему нельзя ее делать?
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
21.12.2011, 10:20 #15
Цитата Сообщение от Toshkarik Посмотреть сообщение
Так я же и спросил про перестановку, про нее в задании ничего не сказано, тогда почему нельзя ее делать?
ну вроде как в задании сказано только про вычеркивание.

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

Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления"
Помогите с кодом написания задачи, не понимаю как написать классы в классе. ...

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс"
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран...

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания"
Создать класс Книга поля: название книги,количество страниц,год издания...

Определить тип данных "Запись", имеющий поля "Фамилия", "Пол", "Зарплата"
определить тип данных запись имеющий поля фамилия пол зарплата. определить...


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

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
Опции темы

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