IMHO.WS

IMHO.WS (http://www.imho.ws/index.php)
-   Программирование (http://www.imho.ws/forumdisplay.php?f=40)
-   -   Помогите!!! Срочно нужно решить одну задачку на С! Плиз!!! (http://www.imho.ws/showthread.php?t=33605)

Izzyy 03.07.2003 02:27
Помогите!!! Срочно нужно решить одну задачку на С! Плиз!!!
 
:idontnow:
Нужно решить задачу следущего типа
дано:

заголовок ф-ции
int check_alpha(char *s1, char *s2)

функция должна проверять есть ли заглавные буквы что находятся в s1 также и в s2 при этом они должни быть в одном и том же порядке если да то возвращает 1 нет 0.
пример

check_alpha("12AbBC54","A76B87C9")=1
check_alpha("12AbBC54","AABBCC")=1
check_alpha("12AAbBC54","ABC")=0
check_alpha("12AbBC54","ACBB)=0

Izzyy 03.07.2003 02:29
Забыл сказать
 
ф-ция обязана быть рекурсивной

SapeR 03.07.2003 02:53
Код:
int check_alpha(char *s1, char *s2)
{
    char *ss1=s1, *ss2=s2;
    int cmp1=0,cmp2=0;

    if (!s1 && !s2) return 1; // <<<<<<<<<<< OK
    if (*s1>='A' && *s1<='Z') cmp1=1;
    if (*s2>='A' && *s2<='Z') cmp2=1;
    if (cmp1 && cmp2 && *s1!=*s2) return 0; // <<<<<<<<< FAIL
    if (!cmp1 && *s1!='\0') ss1++;
    if (!cmp2 && *s2!='\0') ss2++;
    return check_alpha(ss1,ss2);  // <<<<<<<< recursion call
}

Izzyy 03.07.2003 04:19
не вышло
 
печально, но функция не работает просто виснет да даже если бы и не висла в ней есть ошибки, но все равно спасибо, ты меня на мысль натолкнул посмотрим, что получиться.
еще рз спасибо за помощь!

SapeR 03.07.2003 09:14
ой,перепутал !!!
поменяй
if (!s1 && !s2) return 1;
на
if (s1=='\0' && s2=='\0') return 1;

Izzyy 03.07.2003 09:59
Увы....
 
к сожалению эта замена не решает проблемы, т.к. ф-ция все равно входит в бесконечную рекурсию как только находит две одинаковых больших буквы. сейчас буду думать, что нужно изменить чтобы этого не происходило. если будут идеи пиши.

SapeR 03.07.2003 10:01
предпоследняя строка:

if (cmp1 && cmp2) {ss1++; ss2++;}

Izzyy 03.07.2003 10:40
снова нет
 
эту строчку я еще сначала добавил только это не решает проблему тут имхо подход не совсем верный, как мне кажется тут нужно сделать, что то типа цикла. кроме того когда функция доходит до "/0" она у тебя возвращает 1, даже если не все буквы совпадают.
как мне кажется тут нужно делать проверку в цикле
взять букву i в первом слове и сравнивать в цикле с буквами i,i+1,i+2,...i+n во втором до тех пор пока не находит совпадение как только есть совпадение то увеличить i на 1 и заново начать проверку только во втором слове уже продолжать с i+n.
т.к. нужно чтобы еще и порядок совпадал. проблема только в одном я не знаю как это реализовать, да и сам алгоритм не точный.

alexey_ma 03.07.2003 21:43
check_alpha("12AbBC54","AABBCC")=1
Помоему должен быть 0, поскольку порядок не тот, во второй строке не подстроки ABC.
Ну а с циклами можешь попробовать примерно так:
Код:
int check_alpha(char *s1, char *s2)
{
        int i=0;
        int j=0;
        char* ss1=s1;
        char* ss2=s2;
        int res=0;
        for (*ss1;*ss1;ss1++)
        {               
                if (*ss1>='A' && *ss1<='Z')
                        i++;
                else
                        continue;

                for(*ss2;*ss2;ss2++)
                {                       
                        if (*ss2>='A' && *ss2<='Z')       
                                j++;
                        else
                                continue;
                        if(*ss1==*ss2 && j==i)
                        {                                       
                                res++;
                                ss2++;                               
                                break;
                        }
                        else
                        {
                                res=0;
                                ss2++;       
                                return check_alpha(s1,ss2);
                       
                        }
                }
        }
        if(res==i)
                return 1;
        return 0;
}

Machine 04.07.2003 00:39
alexey_ma
Цитата:
check_alpha("12AbBC54","AABBCC")=1
Помоему должен быть 0, поскольку порядок не тот, во второй строке не подстроки ABC.
Порядок тот: A, B, C. Имеется в виду, что между ними могут быть любые символы.

Очень сложно ты написал. По-моему работать не будет, хотя проследить алгоритм мне неподсилу.

Цитата:
return check_alpha(s1,ss2);
А энто зачем?

Вот мой вариант:
Код:
int f(const char *s1, const char *s2)
{
    if(!s1 || !s2)
        return 0;
 
    while(*s1 != '\0'){
   
        if(!isupper(*s1)){
            s1++;
          continue;
        }
   
        while(*s2 != '\0'){

            if(*s2 == *s1)
                break;
     
            s2++;
        }
   
        if(*s2 == '\0')
            return 0;
   
        s1++;
    }

    return 1;
}

alexey_ma 04.07.2003 01:03
Хорошо. Но есть ошибка.
У тебя для ("12AAbBC54","ABC") будет 1, а должен быть 0;


return check_alpha(s1,ss2);
A эту пургу я написал потому-что заказчик рекурсию просил :)

Machine 04.07.2003 01:30
alexey_ma
Цитата:
У тебя для ("12AAbBC54","ABC") будет 1, а должен быть 0;
Поймал таки =)))

Ладно, тогда так:
Код:
int f(const char *s1, const char *s2)
{
    if(!s1 || !s2)
        return 0;
 
    while(*s1 != '\0'){
   
        if(!isupper(*s1)){
            s1++;
          continue;
        }
   
        while(*s2 != '\0'){

            if(*s2 == *s1)
                break;
     
            s2++;
        }
   
        if(*s2 == '\0')
            return 0;
        else
            s2++;
   
        s1++;
    }

    return 1;
}

Machine 04.07.2003 01:33
Цитата:
A эту пургу я написал потому-что заказчик рекурсию просил :)
=)
Странная была просьба. Таки вещи нельзя через рекурсию делать.

alexey_ma 04.07.2003 01:41
Полностью с тобой согласен .
Но Izzyy писал
>> Забыл сказать
>> ф-ция обязана быть рекурсивной

Machine 04.07.2003 02:19
alexey_ma
Препод наверное обкуренный был, когда задачку диктовал =)) Или не шарит в этом нифига...

Izzyy 07.07.2003 20:23
Спасибо
 
спасибо большое за предложеные решения и объяснения, препод он может и накуреный был, только вот его задача научить, а тема рекурсия была.:idea:
и еще to alexey ты не мог бы свой алгоритм пояснить

alexey_ma 07.07.2003 22:40
А чего там пояснять? Ты же сам все написал.
Проходишь по массивам. i и j - это порядковый номер символа в массиве.
Проверкой "*ss1>='A' && *ss1<='Z' отсекаем все маленькие буквы.
Если "if(*ss1==*ss2 && j==i)" то есть буквы равны и их порядковые номера равны - делаем брейк и переходим к следующему символу в первом массиве если нет то продвигаем указатель во втором массиве и рекурсивно вызываем функцию.
Только криво все это. Рекурсия за уши притянута, она здесь не нужна . Machine сделал все правильно и красиво.

Machine 08.07.2003 02:22
Izzyy
Цитата:
только вот его задача научить, а тема рекурсия была.
Дело в том, что для темы "рекурсия" он подобрал очень неудачные примеры. Это не правильно - учить какому-то методу, демонстрируя его использование там, где оно совсем не нужно. А ты научишься и будешь ее использовать где не надо. И кстати вещь эта очень не безобидная с точки зрения производительности...

Он вам давал какие-нибудь задачки по обоработке деревьев, например?

alexey_ma 08.07.2003 10:19
2Izzyy
Вот еще вариант как можно рекурсивно сделать:
Код:
int check_alpha(char *s1, char *s2)
{       
        if(!*s1 )
                return 1;
        if (!(*s1>='A' && *s1<='Z'))                               
                return check_alpha(++s1,s2);
        else
        {
                if(!*s2)
                        return 0;
                if (*s2>='A' && *s2<='Z')
                {
                        if(*s1 == *s2)
                                return check_alpha(++s1,++s2);       
                        else
                                return 0;
                }
                else
                        return check_alpha(s1,++s2);
        }
        return 0;       
}
Не уверен что все правильно будет работать. Но принцип понятен.

Izzyy 08.07.2003 21:20
Спасибо, весьма элегантный подход:claps:

alexey_ma 08.07.2003 23:24
Ты где учишься?


Часовой пояс GMT +4, время: 10:40.

Powered by vBulletin® Version 3.8.5
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.