Форум программистов, компьютерный форум CyberForum.ru

Палиндром-ли вся строка - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 32, средняя оценка - 4.91
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
23.03.2011, 01:21     Палиндром-ли вся строка #1
Был сегодня на собеседовании, одно из заданий было определить является-ли строка палиндромом.
Пример строки был задан такой: а роза упала на лапу азора.
Пробелы могут быть несемметричны.
Входная строка не должна меняться.

Я написал там на листочке нечто вроде.

C++
1
2
3
4
5
6
7
8
bool isPal(const std::string& str)
{
    std::string new_str=const_cast<char*>(str.c_str());
    new_str.erase(std::remove(new_str.begin(), new_str.end(), ' '), new_str.end());
    std::string new_str_rev=new_str;
    std::reverse(new_str_rev.begin(), new_str_rev.end());
    return new_str == new_str_rev;
}
На что мне сказали, что условие не выполняется. Ну впринципе конечно да, но ведь исходная строка не меняется никаким макаром.

Подумав сейчас решил написать некий такой вариант. Впринципе определяет по идее, но не уверен в правильности.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
bool isPal(const std::string& one)
{
    for(size_t i=0, j=one.size()-1; i < one.size() && j > 0; ++i, --j)
    {
        if(one[i] == ' ')
            ++i;
        if(one[j] == ' ')
            --j;
        else if(one[i] != one[j])
            return false;
    }
    return true;
}
Ну и еще вопрос на засыпку, почему на собеседованиях просят точный ответ на инструкцию вроде

C++
1
2
int i=5; 
i=++i + ++i;
И ответ, что это UB почему-то не котируется.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ma3a
Эксперт C++
612 / 456 / 31
Регистрация: 28.01.2011
Сообщений: 605
23.03.2011, 01:41     Палиндром-ли вся строка #2
Цитата Сообщение от ForEveR Посмотреть сообщение
C++
1
2
int i=5; 
i=++i + ++i;
И ответ, что это UB почему-то не котируется.
Вообще говоря, странно, но всё же сам как-то пробовал посмотреть, в какой же ассемблерный листинг это дело выливается в плюсах(компиль от msvc) и вышло нечто вроде

Assembler
1
2
3
4
5
6
mov esi,05h
inc esi
inc esi
mov eax,esi
add eax,esi
mov esi,eax
то бишь сначала делаются 2 инкремента и только потом сложение, таким образом, результат выйдет 14.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
23.03.2011, 01:44  [ТС]     Палиндром-ли вся строка #3
Ma3a, Да, я на MSVS запускал тоже 14.
Но так как тут нету точки следования, то по идее такое выражение не является корректным ибо два или более раз изменяется одна и та же переменная.
Ma3a
Эксперт C++
612 / 456 / 31
Регистрация: 28.01.2011
Сообщений: 605
23.03.2011, 02:08     Палиндром-ли вся строка #4
За определенный результат исполнения этого, конечно, ручаться нельзя, но всё-таки с этой данностью придется смириться и называть число, получающееся на большем количестве компиляторов Не проверял, но наверняка в иных языках, особенно крутящихся на виртуальных машинах со стековым исполнением, результат будет скорее 13, так как там просто по структуре кода придется сначала вычислять каждый из операндов и своевременно класть в стек значения операций, так что сначала первый i будет 6, а второй i отдаст 7. Впрочем, это лишь догадки.
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2294 / 1664 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
23.03.2011, 09:46     Палиндром-ли вся строка #5
Цитата Сообщение от ForEveR Посмотреть сообщение
И ответ, что это UB почему-то не котируется.
Чем обосновали, что ответ про UB некорректен?
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
23.03.2011, 11:41     Палиндром-ли вся строка #6
Веселее, когда
C++
1
i = i++ + ++i;
или
C++
1
i = ++i + i++;
или вообще
C++
1
i += i++ + ++i;
На самом деле совершенно дурацкие вопросы. Ни один вменяемый программист такого в своей программе специально не напишет.
Saiberg
 Аватар для Saiberg
19 / 19 / 1
Регистрация: 23.09.2010
Сообщений: 193
23.03.2011, 11:54     Палиндром-ли вся строка #7
а что в нем не корректного ?

i=++i + ++i;

1) ++i
2) ++i
3) i + i

приоритет операторов задан стандартом
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
23.03.2011, 12:06     Палиндром-ли вся строка #8
C++
1
2
3
int i = 5;
i += i++ + ++i;
//или   i += ++i + i++;
В уме я сосчитал не правильно.(
Ответ будет 19.
grrrrr
 Аватар для grrrrr
45 / 45 / 7
Регистрация: 21.04.2009
Сообщений: 265
23.03.2011, 12:17     Палиндром-ли вся строка #9
у меня wxDev-C++
C++
1
2
int i=5;
i=++i + ++i;
показывает 13. Также как и подсчитал в уме.
Dexter
 Аватар для Dexter
284 / 144 / 16
Регистрация: 13.10.2009
Сообщений: 164
23.03.2011, 12:19     Палиндром-ли вся строка #10
Цитата Сообщение от Deviaphan Посмотреть сообщение
C++
1
2
3
int i = 5;
i += i++ + ++i;
//или   i += ++i + i++;
В уме я сосчитал не правильно.(
Ответ будет 19.
У меня VS 2010

Показывает 17, не пойму откуда 17 =)

...
Вообще странно - в консольном варианте 19, а в winform 17
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
23.03.2011, 12:20     Палиндром-ли вся строка #11
Цитата Сообщение от grrrrr Посмотреть сообщение
показывает 13.
В целях оптимизации, компилятор предпочёл считать с ошибками.) Векторные вычисления такие векторные.)
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
23.03.2011, 12:57  [ТС]     Палиндром-ли вся строка #12
CyBOSSeR, Написал, что UB и будет предположительно 13...
Второй пример был

C++
1
i=((++i)++) + i;
Снова сказал, что пример не корректен и написал что ответ предположительно 12-13... На что мне сказали, это как это ответ 12 минус 13 и вообщем забили разбираться.
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2294 / 1664 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
23.03.2011, 13:29     Палиндром-ли вся строка #13
Цитата Сообщение от Saiberg Посмотреть сообщение
а что в нем не корректного ?
Переменная i модифицируется дважды не переходя через точку следования, что по стандарту есть UB.

Цитата Сообщение от Dexter Посмотреть сообщение
Вообще странно - в консольном варианте 19, а в winform 17
Ничего странного, ибо результат операции не определен с точки зрения стандарта.
Хотя насчет C++/CLI не в курсе, есть ли стандарт и что в нем оговорено.
Ma3a
Эксперт C++
612 / 456 / 31
Регистрация: 28.01.2011
Сообщений: 605
23.03.2011, 17:55     Палиндром-ли вся строка #14
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
Хотя насчет C++/CLI не в курсе, есть ли стандарт и что в нем оговорено.
А всё то же самое оговорено, там ссылаются на стандарт C++, на самом деле.Посмотрел в стандарте ECMA 372, относящемся к спецификации языка C++/CLI, так вот в случае операций инкремента/декремента над свойствами и индексаторами есть кое-какие модификации, но оно и понятно, что get,set, все дела, а во всех остальных случаях идет просто отсылка к стандарту обычного C++.
The operator is processed as specified by Standard C++
Так что поведение должно быть эквивалентным, такой же UB и выйдет.
rangerx
1908 / 1517 / 139
Регистрация: 31.05.2009
Сообщений: 2,876
23.03.2011, 23:56     Палиндром-ли вся строка #15
Цитата Сообщение от ForEveR Посмотреть сообщение
Я написал там на листочке нечто вроде.
Достаточно было использовать std::remove_copy_if и std::equal(если говорить об алгоритмах).
Цитата Сообщение от ForEveR Посмотреть сообщение
Подумав сейчас решил написать некий такой вариант. Впринципе определяет по идее, но не уверен в правильности.
При наличии нескольких подряд идущих пробелов это работать не будет. И условие конечное у тебя не совсем правильное... Сравнение должно продолжаться до тех пор пока i < j.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
24.03.2011, 00:00  [ТС]     Палиндром-ли вся строка #16
rangerx, Ну да. Но пробелы для этого несколько мешают насколько я понимаю.
А про std::equal да согласен. Спасибо)
rangerx
1908 / 1517 / 139
Регистрация: 31.05.2009
Сообщений: 2,876
24.03.2011, 12:04     Палиндром-ли вся строка #17
Цитата Сообщение от ForEveR Посмотреть сообщение
Но пробелы для этого несколько мешают насколько я понимаю.
Не мешают. Подумай хорошо над алгоритмом.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
24.03.2011, 13:34  [ТС]     Палиндром-ли вся строка #18
rangerx, Пока делать нечего решил попробовать написать снова.

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
#include <iostream>
#include <string>
 
bool isPal(const std::string& to_c)
{
    for(int i=0, j=to_c.size()-1; i < j;)
    {
        if(to_c[i] == ' ')
        {
            ++i;
            continue;
        }
        if(to_c[j] == ' ')
        {
            --j;
            continue;
        }
        else if(to_c[i] != to_c[j])
            return false;
        ++i;
        --j;
    }
    return true;
}
 
int main()
{
    std::locale().global(std::locale(""));
    std::cout<<isPal("а         роз   а упа    ла на лапу а    зо     ра");
}
Больше похоже на правду?
rangerx
1908 / 1517 / 139
Регистрация: 31.05.2009
Сообщений: 2,876
24.03.2011, 15:38     Палиндром-ли вся строка #19
Да, но я написал бы как-то так(без всяких continue)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool isPal(const std::string& s)
{
    // с учётом того что строка может содержать одни пробелы или быть пуста
    std::string::size_type i = s.find_first_not_of(' ');
    if(i == std::string::npos) return false;
    std::string::size_type j = s.find_last_not_of(' ');
 
    while (i < j)
    {
        if (s[i] == ' ') ++i;
        else if (s[j] == ' ') --j;
        else if (s[i++] != s[j--]) return false;
    }
 
    return true;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.03.2011, 21:21     Палиндром-ли вся строка
Еще ссылки по теме:

Для всех и вся - Компилятор и IDE! C++
C++ Дана строка. Определить минимальное количество символов, которые нужно добавить, чтобы получить палиндром
C++ Очищается ли вся динамическая память по завершению программы?

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

Или воспользуйтесь поиском по форуму:
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
24.03.2011, 21:21  [ТС]     Палиндром-ли вся строка #20
Сегодня был на собеседовании - больше понравилось. Были 3 задачки по почте - сделал. Около 10-15 кодов на самом собеседовании (нужно было исправить или дописать). И тест brainbench - 4.5 балла вышло) Приняли)
Yandex
Объявления
24.03.2011, 21:21     Палиндром-ли вся строка
Ответ Создать тему
Опции темы

Текущее время: 09:26. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru