C++ проверить - можно ли из одной строки с помощью перестановок получить другую
Primary tabs
напомню, что наше рассуждение начиналось здесь
для начала распишем логику алгоритма:
1) проверим что длины строк равны (используем эту функцию) - просто напишем что-то вроде
if (strlen(str1)==strlen(str2)) {// продолжаем работать} else {} // прерываем работу программы
2) нам надо понять - достаточно ли необходимых символов во второй строке чтобы получить первую - с точки зрения логики (долго не думая) - это проще всего организовать вложив один цикл в другой:
- пробегаем циклом по одной из строк - пусть она называется "первая" строка
- внутри цикла перебора первой строки располагаем цикл перебора второй строки
нам надо убедится, что каждый символ из первой строки (внешний) цикл - встречается во второй строке (её мы будем полностью перебирать столько раз сколько символов в первой строке - так как перебор второй строки у нас вложенный)
столько же раз - сколько он встречается в первой - в противном случае - мы выходим из цикла - и выбрасываем сообщение о том, перестановку выполнить не возможно.
делается это как-то так:
int m = 0; // изначально на первый элемент int n = 0; // для второй строки тоже ine c1 = 1; // количество вхождений некоторого символа // в первую строку (один символ //может встречать в строке несоколько раз) int x = 1;// признак пригодности строк для перестановки // по-умолчанию -пригодный (поднимаем флаг в единицу - /* далее в цикле мы опустим его в ноль если какое-нибудь условие не выполнится*/ // поехали while (str1[m] != 0) // условие перебора { /*узнаём сколько раз очередной символ из первой строки встречается в этой же самой первой строке - для этого мы применяем собственную функцию - она принимает два параметра - первый- это символ типа char, а второй - это массив char-ов - то есть строка. */ c1 = how_many_symb_in_str(str1[m],str1);// эту функцию надо реализовать - /*то есть перебрать передаваемую строку сравнив каждый символ с первыым переданным параметром - и вернуть число совпадений*/ n = 0;// обнуляем счётчик внутреннего цикла (чтобы каждый раз начинать сначала) int с2 = 0;// число вхождений некоторого символа во вторую строку while (str2[n] != 0) { if (str2[n] == str1[m]) с2++; // фиксируем, что встретили такой же символ n++; } /*сверяем число вхождений символа в первую и вторую строку*/ if (c2 != c1) { x = 0;// опускаем флаг - число символом одного типа не совпадает break;//прерываем выолнение цилкла - так как // дальнейшая проверка бессмысленна } m++; // переходим к следующему индексу // вращаем внешний цикл снова } /*прежде чем продолжать проверим результат работы цикла*/ if (x==1) { // продолжаем работать } else {} //выводим сообщение об ошибке.
ПРИМЕЧАНИЕ:
факически блок
n = 0;// обнуляем счётчик внутреннего цикла (чтобы каждый раз начинать сначала) int с2 = 0;// число вхождений некоторого символа во вторую строку while (str2[n] != 0) { if (str2[n] == str1[m]) с2++; // фиксируем, что встретили такой же символ n++; }
- и есть реализация (одна из возможных) функции how_many_symb_in_str() - а потому - его можно заменить на вызов функции для второй строки.
Реализуйте эту часть задачи (пару раз проверив на тесте) - и пойдём дальше)
- Log in to post comments
- 52960 reads
baton
Wed, 01/09/2013 - 22:09
Permalink
пара замечаний - из условия
пара замечаний - из условия вытекает, что строки должны быть равны по длине, а так же кол-во символов, подлежащих перестановке должно быть равным в обоих строках.
ну че, буду думать.
vedro-compota
Wed, 01/09/2013 - 22:16
Permalink
да - верно - сначала прежде
да - верно - сначала прежде всего надо проверить на то, что длины строк равны - ща поправлю рассуждение выше.
_____________
матфак вгу и остальная классика =)
baton
Wed, 01/09/2013 - 23:34
Permalink
благодарю
чтож, спасибо, постараюсь завтра разобраться.
один вопрос - функцию how_many_symb_in_str(str1[m],str1) "надо реализовать" - она отдельно описывается, я так понимаю?
о результатах отпишусь
vedro-compota
Wed, 01/09/2013 - 23:53
Permalink
да. она описывается отдельно
да. она описывается отдельно (по структуре любая функция похожа на функцию main) + ещё надо будет вынести её описание.
очень полезно будет почитать это = http://fkn.ktu10.com/?q=node/3384
_____________
матфак вгу и остальная классика =)
baton
Thu, 01/10/2013 - 15:47
Permalink
понял
не, я умею описывать функции - просто уточнил, что это неописанная функция нуждающаяся в описании))))))))))))))))))))
за ссылки спасибо - я там нового нашел немного - но сам ресурс весьма полезный.
для сравнения длин строк будет использована функция:
_____________________________________________
Источники(читать подробнее)=
Ключевые слова и фразы(для поиска)=http://www.cplusplus.com/reference/cstri...
конкретно функция будет представлять что-то вроде:
уточнение - вторая функция, выводящая х на экран, написана для иллюстрации. я заюзаю первую функцию два раза с разными переменными, потом сравню возвращаемые значения длин строк и дальше - прерывание или продолжение (если равны) программы
vedro-compota
Thu, 01/10/2013 - 19:49
Permalink
по-идее функция должна быть
по-идее функция должна быть универсальна - то есть принимать два параметра - ничего на экран не выводить - это точно
_____________
матфак вгу и остальная классика =)
baton
Thu, 01/10/2013 - 20:03
Permalink
значит мое умение составлять
значит мое умение составлять функции на высоте...........
vedro-compota
Thu, 01/10/2013 - 20:05
Permalink
ваша функция работает?
ваша функция работает? реализация уже фактически была приведена выше.
_____________
матфак вгу и остальная классика =)
vedro-compota
Thu, 01/10/2013 - 20:12
Permalink
например функция может
например функция может выглядеть так:
_____________
матфак вгу и остальная классика =)
baton
Thu, 01/10/2013 - 20:49
Permalink
слушай, как мы привязываем
слушай, как мы привязываем simb к другой строке?
туплю, но снизойдите....
по моему разумению это выглядит так:
однако этот цикл может посчитать лишь вхождение только одного символа в строку1 игнорируя вероятность повторения этого символа в строке2
vedro-compota
Thu, 01/10/2013 - 20:30
Permalink
в смысле "привязываем" ?
в смысле "привязываем" ?
если вы про вызов - то он же выше был написан - мы передаём элемент массива - каждый из элементов - типа char - =
кстати - в листиге выше - как уже было выше сказанно внутренний цикл не нужен - достаточно просто вызвать функцию и для второй строки -
типа внутри внешнего цикла просто поставить проверку =
_____________
матфак вгу и остальная классика =)
baton
Thu, 01/10/2013 - 20:51
Permalink
ага
ага
ну я и тупой на исходе дня
а тот цикл что я выше запилил - в мусорку?
короче, в мусорку
vedro-compota
Thu, 01/10/2013 - 20:54
Permalink
ммммм....для начала
ммммм....для начала сформулируйте - что вообще делает функция которую вы написали.
та, что привел я - возвращает число вхождений символа в некоторую строку.
_____________
матфак вгу и остальная классика =)
vedro-compota
Thu, 01/10/2013 - 21:05
Permalink
кстати -
кстати -
это лишь часть зверских причуд. но мне интересно почитать предлагаемый вами алгоритм - точнее описание того,что здесь написано)
_____________
матфак вгу и остальная классика =)
baton
Thu, 01/10/2013 - 21:36
Permalink
это был загон - когда шарики
это был загон - когда шарики за ролики....
я решил, что предлагаемый вам код слишком сложен для моего самостоятельного написания - препод не поверит - и поэтому сделал последню попытку родить оригинальное извращение над строками.
данная функция проверяет наличие одинаковых символов в строках, уже проверенных на равенство длинны:
уже запиливая комментарий я осознал, что цикл не подсчитывает количество вхождений одинаковых символов и не проверяет равенство этих вхождений в строках...
придется все же сдать эти зверства в кунсткамеру.....
vedro-compota
Thu, 01/10/2013 - 21:40
Permalink
моя функция - это довольно
моя функция - это довольно тривиальное решение, рассчитанное на сравнение строк не очень большой длинны.
если бы строки были по пару миллионов символов - то имело бы смысл - создавать массив уже проверенных символов -чтобы не запускать каждый раз подсчёт числа вхождений для каждого символа - в случае если обе строки уже были проверены для точно такого же символа ранее.
так что моя функция вполне себе обычна
_____________
матфак вгу и остальная классика =)
baton
Thu, 01/10/2013 - 21:55
Permalink
н-да
тривиальное для курса на котором вы учитесь (а возможно уже отучились), но не для дибила-первака-меня ((((((((((((((((((((((((((((((((((
хотя я, в принципе, понял вашу функцию.
юзаю в неизменном виде - какой же я тупой.......
поясните еще - str2 не заявлена в аргументах функции - поэтому меня беспокоит строка:
vedro-compota
Thu, 01/10/2013 - 21:59
Permalink
это опечатка .
это опечатка .
следует исправить на =
_____________
матфак вгу и остальная классика =)
baton
Thu, 01/10/2013 - 23:02
Permalink
int how_many_symb_in_str(char
vedro-compota
Thu, 01/10/2013 - 23:26
Permalink
int checkArray(char *str1,
зачем это?..........
функция которая считает число вхождений уже даёт нам инфу о наличии символа или его отсутствии =
_____________
матфак вгу и остальная классика =)
vedro-compota
Fri, 01/11/2013 - 00:02
Permalink
оформляем проверку
как отдельная функция =
_____________
матфак вгу и остальная классика =)
baton
Fri, 01/11/2013 - 00:25
Permalink
дальше
протупив около.. не знаю, сколько времени я тупил над готовым по сути кодом - благословясь приступаем к перестановке символов.
там я тоже собираюсь тупануть - т.к. это может занять много места, создаю следующую тему - http://fkn.ktu10.com/?q=node/3397