7 / 7 / 3
Регистрация: 19.10.2014
Сообщений: 92
1

Количество способов преобразования строки путём вычёркивания символов

29.10.2014, 17:05. Показов 1426. Ответов 15
Метки нет (Все метки)

Есть две строки Х и У, в которых содержатся только буквы латинского алфавита и цифры (длинны не превышают 30 символов).Сначала вводится 1-я строка, затем вторая. Прошу помочь реализовать программу , которая считает количество способов, которыми можно получить У из Х , применяя только вычеркивани символов.

Например,

Ввод1: aaabbbbccc
abc
Вывод1: 36

Ввод2: abcabc
abc
Вывод2: 4



Буду благодарен за любую помощь
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.10.2014, 17:05
Ответы с готовыми решениями:

Можно ли строку получить из другой строки путем вычеркивания некоторых символов?
Помогите, пожалуйста, решить задачку. даны две строки st1 и st2 . выяснить, можно ли строку st2...

Выяснить, можно ли строку st2 получить из строки st1 путем вычеркивания некоторых символов
Даны две строки st1 и st2. Нужно выяснить, можно ли строку st2 получить из строки st1 путем...

Получить 2 строку из 1 путем вычеркивания символов
Даны две строки st1 и st2. Нужно выяснить, можно ли строку st2 получить из строки st1 путем...

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

15
65 / 65 / 16
Регистрация: 07.04.2014
Сообщений: 332
29.10.2014, 17:11 2
Задача прикольная, когда то такое делал на чистом C. делать лень. могу алгоритм написать буквами
0
7 / 7 / 3
Регистрация: 19.10.2014
Сообщений: 92
29.10.2014, 20:32  [ТС] 3
fidgi, опишите алгоритм, пожалуйста.
0
65 / 65 / 16
Регистрация: 07.04.2014
Сообщений: 332
29.10.2014, 22:28 4
на примере строки Y - abc

1) for`ите строку X и ищите букву `a`.
2) Как нашли с этого места ищите букву b.
3) Как нашли `b` ищите `c`.
4) Если нашли, то "количество способов+1".
5) Далее продолжаете искать буквы `с`.
6) Если находите то "количество способов++".
7) Как строка закончится вернуться к шагу 2
8) Как закончатся все 'b' вернуться к шагу 1 и искать следующую a
0
7 / 7 / 3
Регистрация: 19.10.2014
Сообщений: 92
29.10.2014, 23:50  [ТС] 5
fidgi, мягко говоря , часть просто не понял (из-за своего мизерного опыта в сфере программирования ). Как мы вводим переменную "количество способов" и как ищем в строке Х нужный нам символ из Y?
0
65 / 65 / 16
Регистрация: 07.04.2014
Сообщений: 332
30.10.2014, 10:27 6
Цитата Сообщение от Superbeginner Посмотреть сообщение
Как мы вводим переменную "количество способов"
C#
1
private int counter=0;
Цитата Сообщение от Superbeginner Посмотреть сообщение
как ищем в строке Х нужный нам символ из Y?
С помощью цикла for() и условий if()

В этой теме -> FAQ для студентов или школьников есть примеры работы с массивами
0
7 / 7 / 3
Регистрация: 19.10.2014
Сообщений: 92
31.10.2014, 23:39  [ТС] 7
fidgi, можете подсказать, как оптимизировать программу ( нужно уменьшить время работы) ?

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
{
string A = Console.ReadLine();
string B = Console.ReadLine();
 
Console.WriteLine(f(A, B));
Console.ReadKey();
}
 
static int f(string A, string B)
{
if (A.Length < B.Length)
return 0;
if (A == B)
return 1;
 
int result = 0;
 
for (int i = 0; i < A.Length; i++)
if (A[i] == B[0])
if (B.Length == 1)
result++;
else
result += f(A.Substring(i + 1), B.Substring(1));
 
return result;
}
0
65 / 65 / 16
Регистрация: 07.04.2014
Сообщений: 332
01.11.2014, 03:10 8
Superbeginner, время работы? А что с ним не так? Тут времени работы меньше милисекунды.
Делайте шапку получше и всё.
Решение элегантное кстати.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private static void Main(string[] args)
        {
            string sourceString;
 
            Console.WriteLine("Введите строку в которой будет производиться поиск");
            do
            {
                sourceString = Console.ReadLine();
            } while (sourceString == null);
            
            Console.WriteLine("Введите поисковую строку");
            var searchString = Console.ReadLine();
 
            while (searchString != null && searchString.Length >= sourceString.Length)
            {
                Console.WriteLine("некорректный ввод поисковой строки. попробуйте ещё раз");
                searchString = Console.ReadLine();
            }
 
            Console.WriteLine("Найдено комбинаций: {0}", Counting(sourceString, searchString));
            Console.ReadKey();
        }
0
7 / 7 / 3
Регистрация: 19.10.2014
Сообщений: 92
01.11.2014, 16:15  [ТС] 9
fidgi,спасибо . Но программа не предолевает временной лимит выполнения этой программы . Не могу понять в чём причина.
0
65 / 65 / 16
Регистрация: 07.04.2014
Сообщений: 332
01.11.2014, 16:55 10
Странно. А какой лимит и где функции проверки времени исполнения?

Проблема же может быть в том что каждый раз при вызове f происходит ненужная проверка двух условий if. Перенесите их в main.
Так же причина может быть в рекурсивном вызове функции f (там всякие забития стека бывают. я в этом не особо шарю).
А может встроенные реализации substring много процессорного времени едят.

попробуйте такой вариант. накидал вчера ночью.
Кликните здесь для просмотра всего текста
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
private static void Main(string[] args)
        {
            string sourceString;
 
            Console.WriteLine("Введите строку в которой будет производиться поиск");
            do
            {
                sourceString = Console.ReadLine();
            } while (sourceString == null);
            
            Console.WriteLine("Введите поисковую строку");
            var searchString = Console.ReadLine();
 
            while (searchString != null && searchString.Length >= sourceString.Length)
            {
                Console.WriteLine("некорректный ввод поисковой строки. попробуйте ещё раз");
                searchString = Console.ReadLine();
            }
 
            Console.WriteLine("Найдено комбинаций: {0}", Counting(sourceString, searchString));
            Console.ReadKey();
        }
 
        private static int Counting(string sourceString, string searchString)
        {
            var result=0;
            var counter = 0;
            var j = 0;
 
            for (var i = 0; i < searchString.Length; i++)
            {
                for (; j < sourceString.Length; j++)
                {
                    if (sourceString[j] == searchString[0])
                    {
                        counter = j;
                        counter++;
                    }
 
                    if ((sourceString[j] == searchString[i]) && i != searchString.Length - 1)
                    {
                        j++;
                        break;
                    }
 
                    if ((sourceString[j] != searchString[i]) || i != searchString.Length - 1) continue;
                    result++;
 
                    if (counter < sourceString.Length - 1)
                    {
                        j = counter;
                        i = -1;
                    }
                    else return result;
 
                    break;
                }
            }
            return result;
        }
0
7 / 7 / 3
Регистрация: 19.10.2014
Сообщений: 92
01.11.2014, 17:05  [ТС] 11
fidgi, благодарю, но Ваша программа работает неправильно

Ввод: aaabbbbccc
abc
Вывод: 36


у Вашей программы вывод в таком случае - 1.
Миниатюры
Количество способов преобразования строки путём вычёркивания символов  
0
65 / 65 / 16
Регистрация: 07.04.2014
Сообщений: 332
01.11.2014, 18:08 12
Да, сейчас проверил и действительно на таком условии не работает) попробовал переделать, слишком геморно. Нормально только с рекурсией будет выглядеть или слишком много костылей.
0
7 / 7 / 3
Регистрация: 19.10.2014
Сообщений: 92
02.11.2014, 00:15  [ТС] 13
fidgi, всё же проблема быстродействия остаёся актуальной.
0
65 / 65 / 16
Регистрация: 07.04.2014
Сообщений: 332
02.11.2014, 01:10 14
скиньте свой проект весь

Добавлено через 43 секунды
и напишите сколько нужно миллисекунд и на каком тестовом задании
0
7 / 7 / 3
Регистрация: 19.10.2014
Сообщений: 92
02.11.2014, 14:43  [ТС] 15
fidgi,лимит времени на задание - 4000 мс.
Тест на котором выдает "time limit" - тест №9 из 20.

Ввод: zaaaaaaaaaaaaaaaaaaaaaaaaaaaaq
zaaaaaaaaaaaaaaq
Вывод: 40116600


Вывод верный, но только на этот тест уходит приблизительно 9 секунд
0
65 / 65 / 16
Регистрация: 07.04.2014
Сообщений: 332
03.11.2014, 03:49 16
ок. завтра попробую что-то сделать
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.11.2014, 03:49
Помогаю со студенческими работами здесь

Получить матрицу, путем вычеркивания с данной матрицы, Н-ой строки и М-го столбика
Ребят, напишите плиз прогу на с++. Условие: Получить матрицу, путем вычеркивания с данной...

Оптимизация строки путем замены символов на символ и его подряд идущее количество
Привет всем. Задача строку типа &quot;000222220123000031200000032223311&quot; преобразовать в...

Шифрование путем преобразования одних символов в другие
Вобщем вопрос такой, ниразу с криптографией не работал, как мне считать текст с RichTextBox...

Сжать массив путем вычеркивания нулевых элементов
Имеется целочисленный массив из n элементов,сжать массив путем вычеркивания нулывех элементов, если...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru