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
- 56863 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
понял
не, я умею описывать функции - просто уточнил, что это неописанная функция нуждающаяся в описании))))))))))))))))))))
за ссылки спасибо - я там нового нашел немного - но сам ресурс весьма полезный.
для сравнения длин строк будет использована функция:
/* strlen example */ #include "stdio.h" #include "conio.h" #include "string.h" int main () { char szInput[256]; printf ( "Enter a sentence: " ); gets (szInput); printf ( "The sentence entered is %u characters long.\n" ,( unsigned )strlen(szInput)); getch () ; return 0; }_____________________________________________
Источники(читать подробнее)=
Ключевые слова и фразы(для поиска)=http://www.cplusplus.com/reference/cstri...
конкретно функция будет представлять что-то вроде:
#include <stdio.h> #include "conio.h" #include <string.h> #include <string> int erere (int x) { char szInput[256]; printf ( "Enter a sentence: " ); gets (szInput); x = ( unsigned )strlen(szInput)); getch () ; return x; } int main (int x){ erere (x); printf ( "The sentence entered is %u characters long.\n" , x); }уточнение - вторая функция, выводящая х на экран, написана для иллюстрации. я заюзаю первую функцию два раза с разными переменными, потом сравню возвращаемые значения длин строк и дальше - прерывание или продолжение (если равны) программы
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
например функция может
например функция может выглядеть так:
/* функция вернёт число вхождений символа simb - (следует понимать ,что можно передать элемент массива - например str[m])*/ int how_many_symb_in_str(char simb,char* str) { int n = 0;// просто счётчик int с2 = 0;// число вхождений некоторого символа simb в строку // изначально устанливаем в ноль while (str[n] != 0) { if (str2[n] == simb) с2++; // фиксируем, что встретили такой же символ n++; // накручиваем счётчик } return с2;// возвращаем число вхождений //которое можно использовать далее "снаружи" }_____________
матфак вгу и остальная классика =)
baton
Thu, 01/10/2013 - 20:49
Permalink
слушай, как мы привязываем
слушай, как мы привязываем simb к другой строке?
туплю, но снизойдите....
по моему разумению это выглядит так:
int how_many_symb_in_str(char simb, char* str1, char* str2){ int n = 0, m = 1;// просто счётчики int с2 = 0; // число вхождений некоторого символа simb в строку // изначально устанливаем в ноль while (str2[n] != 0) simb = str1[m]; { if (str2[n] == simb) {с2++; // фиксируем, что встретили такой же символ n++; // накручиваем счётчик } else m++; // при неравенстве берем следующий символ строки1 } return с2;// возвращаем число вхождений //которое можно использовать далее "снаружи" }однако этот цикл может посчитать лишь вхождение только одного символа в строку1 игнорируя вероятность повторения этого символа в строке2
vedro-compota
Thu, 01/10/2013 - 20:30
Permalink
в смысле "привязываем" ?
в смысле "привязываем" ?
если вы про вызов - то он же выше был написан - мы передаём элемент массива - каждый из элементов - типа char - =
кстати - в листиге выше - как уже было выше сказанно внутренний цикл не нужен - достаточно просто вызвать функцию и для второй строки -
типа внутри внешнего цикла просто поставить проверку =
if ((how_many_symb_in_str(str1[m],str1) == how_many_symb_in_str(str1[m],str2)) { //продолжаем цикл } else { // опускаем флаг - и вызываем break - чтобы зря не гнать цикл дальше //- так как одна буква уже некорректна }_____________
матфак вгу и остальная классика =)
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
кстати -
кстати -
while (str2[n] != 0) simb = str1[m]; // этол цикл { // а дальше уже не цикл if (str2[n] == simb) {с2++; // фиксируем, что встретили такой же символ // ПОЧЕМУ ПРОВЕРКА 2-ОЙ СТРОКИ КОГДА ИЩЕМ В ПЕРВОЙ?(судя по вашим словам) n++; // накручиваем счётчик } else m++; // при неравенстве берем следующий символ строки1 } return с2;// возвращаем число вхождений //которое можно использовать далее "снаружи"это лишь часть зверских причуд. но мне интересно почитать предлагаемый вами алгоритм - точнее описание того,что здесь написано)
_____________
матфак вгу и остальная классика =)
baton
Thu, 01/10/2013 - 21:36
Permalink
это был загон - когда шарики
это был загон - когда шарики за ролики....
я решил, что предлагаемый вам код слишком сложен для моего самостоятельного написания - препод не поверит - и поэтому сделал последню попытку родить оригинальное извращение над строками.
данная функция проверяет наличие одинаковых символов в строках, уже проверенных на равенство длинны:
int checkArray(char *str1, char *str2){ // проверка наличия одинаковых символов int n = 0, m = 0, x; while((str1[n] != 0) || (str2[m] != 0)){ // проверка наличия одинаковых символов m = 0; // счетчик каждый раз обнуляется - счет с нулевого члена if(str1[n] == str2[m]){ //если Nный символ строки1 = Mному -> // -> символу строки2, то m+1 -> m++; // -> берется (m+1)ный символ стр1 на случай повтора символа if(str2[m] = 0) // а рано или поздно он будет = 0. n++; // тогда берется следующий член строки1 else m++; // иначе берется следующий член строки2 } if ((str2[m] = 0) && (str1[n] != str2[m])){ // если один из символов строки1 неравен - // - ни одному символу строки2, х=0, выпад из цикла x = 0; break; } else x = 1; // иначе х = 1, цикл продолжается до выполнения своего условия } return x; }уже запиливая комментарий я осознал, что цикл не подсчитывает количество вхождений одинаковых символов и не проверяет равенство этих вхождений в строках...
придется все же сдать эти зверства в кунсткамеру.....
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
int how_many_symb_in_str(char simb,char* str) // наша полюбившеяся функция { int n = 0;// просто счётчик int с2 = 0;// число вхождений некоторого символа simb в строку // изначально устанливаем в ноль while (str[n] != 0) { if (str[n] == simb) с2++; // повторение n++; // следующий член } return с2; //число вхождений } int checkArray(char *str1, char *str2){ // проверка наличия одинаковых символов (после проверки длинны строк) int n = 0, m = 0, x, s1, s2, t; while((str1[n] != 0) || (str2[m] != 0)){ // цикл по проверке наличия одинаковых символов // условие перебора /* узнаём сколько раз очередной символ из первой строки встречается в этой же первой строке - применяем функцию how_many_symb_in_str(символ char,массив char) */ s1 = how_many_symb_in_str(str1[m],str1); t = 0;// обнуление счётчикa внутреннего цикла int с2 = 0;// число вхождений символа во вторую строку while (str2[t] != 0){ s2 = how_many_symb_in_str(str1[m],str2); if (str2[t] == str1[m]) { с2++; // фиксируем обнаружение такого же символа x=1; } t++; // берется следующий член строки2 if (с2 != s1) { //сверяется число вхождений символа в первую и вторую строку x = 0; break; // выпадение } m++; // берется следующий член строки1 if (x!=1) { // проверка условия равенства совпадений в строках break; //выпад printf("невозможно выполнить перестановку - есть разные символы"); //сообщение об ошибке. } } } return x; }vedro-compota
Thu, 01/10/2013 - 23:26
Permalink
int checkArray(char *str1,
int checkArray(char *str1, char *str2){ // проверка наличия одинаковых символов (после проверки длинны строк)зачем это?..........
функция которая считает число вхождений уже даёт нам инфу о наличии символа или его отсутствии =
int x = 1;// флаг по-умолчанию поднят // сначала проверим что длины строк равны = if (strlen(str1) == strlen(str2)) { while (str1[m] != 0) { // проверям if ((how_many_symb_in_str(str1[m],str1) == how_many_symb_in_str(str1[m],str2)) m++; else { x = 0; break; // выхожим из цикла } } } else x = 0; // опять же - опускаем флаг /* ПОЯСНЕНИЕ: если строки одинаковой длинны - т.е - (strlen(str1) == strlen(str2)) и при этом каждый символ встречает во второй строке столько же раз сколько в первое - т.е = (how_many_symb_in_str(str1[m],str1) == how_many_symb_in_str(str1[m],str2)) ТО -значит ПЕРЕСТАНОВКУ ВЫПОЛНИТЬ МОЖНО */_____________
матфак вгу и остальная классика =)
vedro-compota
Fri, 01/11/2013 - 00:02
Permalink
оформляем проверку
как отдельная функция =
checkArray(char *str1, char *str2) { int m = 0; int x = 1;// флаг по-умолчанию поднят // сначала проверим что длины строк равны = if (strlen(str1) == strlen(str2)) { while (str1[m] != 0) { // проверям if ((how_many_symb_in_str(str1[m],str1) == how_many_symb_in_str(str1[m],str2)) m++; else { x = 0; break; // выхожим из цикла } } } else x = 0; // опять же - опускаем флаг return x; // Я ТОЖЕ ВОЗВРАЩАЮ X )))))))) }_____________
матфак вгу и остальная классика =)
baton
Fri, 01/11/2013 - 00:25
Permalink
дальше
протупив около.. не знаю, сколько времени я тупил над готовым по сути кодом - благословясь приступаем к перестановке символов.
там я тоже собираюсь тупануть - т.к. это может занять много места, создаю следующую тему - http://fkn.ktu10.com/?q=node/3397