Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
#1

Рекурсия в различных компиляторах - C++

27.07.2011, 22:29. Просмотров 1502. Ответов 31
Метки нет (Все метки)

Доброго времени суток.
Задача: дано целое число n, нужно получить его битовое представление, развернуть его, и то, что получилось перевести обратно в десятичную систему счисления.
Пример:n = 4, ответ - 1
n = 6, ответ - 3.
Решил ее через циклы, прошла все тесты, поэтому решение меня не интересует.
Также написал красивую на мой взгляд рекурсию, которая отлично работает на gcc.
C++
1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <cmath>
int n, k;
int f(int n){
    return n ? f(n / 2) + n % 2 * pow(2., k++) : 0;
}
int main(){
    int n = 6;
    std::cout << f(n);
}
Но, VC++ этот код неправильно понимает(просто выводит назад это же число).
Собственно, вопрос - что в моей рекурсии неоднозначно? И как ее можно исправить?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.07.2011, 22:29
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Рекурсия в различных компиляторах (C++):

Количество различных цифр в числе рекурсия - C++
для натурального n вывести количество разных цифр, участвовавших в его записи. Помогите составить рекурсивную функцию, я плохо...

Программа не работает на всех компиляторах одинаково - C++
Привет. #include &lt;iostream&gt; using namespace std; void array_sdvig_napravo(int array, int size) { register int temp = array; ...

Почему в программах, компилированных в С++-компиляторах так много лишнего кода? - C++
Здравия всем! Никому не интересное предисловие: Захотел перенсти своего бота с C++ на ассемблер, говорят, так размер уменьшается и...

Две части программы на разных компиляторах - C++
Не знаю, в ту ли тему я пишу свой вопрос :) А состоит он вот в чем. Написал я довольно большое приложение на WinApi. Писал в Visual C++...

Несоответствие работы cin.putback в разных компиляторах - C++
Здравствуйте! Озадачило меня следующее несоответствие (текст приведен в качестве примера): #include &lt;iostream&gt; #include &lt;cstring&gt;...

Работает в онлайн компиляторах, но не работает у меня - C++
Проверяю данные, но на компьютере не работает, в чем роблема? #include &lt;string.h&gt; #include &lt;stdlib.h&gt; #include &lt;stdio.h&gt; ...

31
grizlik78
Эксперт С++
1970 / 1463 / 122
Регистрация: 29.05.2011
Сообщений: 3,029
27.07.2011, 22:40 #2
Цитата Сообщение от diagon Посмотреть сообщение
Собственно, вопрос - что в моей рекурсии неоднозначно?
Порядок вычисления операндов в выражении не определён.
C++
1
f(n / 2) + n % 2 * pow(2., k++)
Видимо в одном случае сначала вычисляется f(n/2) а потом k++, а в другом случае наоборот.
0
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
27.07.2011, 22:45  [ТС] #3
Цитата Сообщение от grizlik78 Посмотреть сообщение
Порядок вычисления операндов в выражении не определён.
C++
1
f(n / 2) + n % 2 * pow(2., k++)
Видимо в одном случае сначала вычисляется f(n/2) а потом k++, а в другом случае наоборот.
Хм... Не понял
По идее первой должна вызываться f(n/2), ну а дальше остальное выражение, там все однозначно вроде.
У % и * приоритет одинаковый, но % должен первым вычисляться, ибо стоит левее.
0
grizlik78
Эксперт С++
1970 / 1463 / 122
Регистрация: 29.05.2011
Сообщений: 3,029
27.07.2011, 22:47 #4
у оператора + 2 операнда. Оба являются выражениями, которые надо вычислить перед сложением. Какой из них будет вычислен первым стандартом не оговаривается. В одном случае сначала вычисляется левое выражение, затем правое. В другом сначала правое, потом левое.
1
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
27.07.2011, 22:52  [ТС] #5
Цитата Сообщение от grizlik78 Посмотреть сообщение
у оператора + 2 операнда. Оба являются выражениями, которые надо вычислить перед сложением. Какой из них будет вычислен первым стандартом не оговаривается. В одном случае сначала вычисляется левое выражение, затем правое. В другом сначала правое, потом левое.
Странно как-то... + вообще последним вычисляться должен, у него же наименьший приоритет.
Но даже если так - как тогда это можно исправить? (Минимальным количеством символов, желательно =) ).
Получается, что нужно как-то повысить приоритет у f(n/2)... Но как это сделать - вопрос...
0
grizlik78
Эксперт С++
1970 / 1463 / 122
Регистрация: 29.05.2011
Сообщений: 3,029
27.07.2011, 22:56 #6
само сложение и вычисляется последним. но операнды можно вычислить двумя способами.
следующие 2 варианта были бы эквивалентны, если бы не побочный эффект в виде изменения k:
первый
C++
1
2
3
4
int f(int n){
    int a, b;
    return n ? a=f(n / 2), b=n % 2 * pow(2., k++), a+b : 0;
}
второй
C++
1
2
3
4
int f(int n){
    int a, b;
    return n ? b=n % 2 * pow(2., k++), a=f(n / 2), a+b : 0;
}
Вот мне представляется, что GCC идёт одним путём (первым?), а MSVC другим.
1
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
27.07.2011, 23:16  [ТС] #7
Да, вы правы, так работает
C++
1
return n ? f(n/2) + n % 2 * pow(2., k), ++k : 0;
Хотя вру. В вышеприведенном коде работает, а в этом нет.
C++
1
2
3
4
5
6
7
8
9
10
#include <fstream>
#include <cmath>
int n, k;
int f(int n){
    return n ? f(n/2) + n % 2 * pow(2., k), ++k : 0;
}
int main(){
    std:: fstream("input.txt") >> n;
    std:: ofstream("output.txt") << f(n);
}
Добавлено через 13 минут
Мда, у студии крышу сносит.
Если объявление n перенести в мейн, то выдает 30, если глобально - 0. А правильно будет 3.
0
grizlik78
Эксперт С++
1970 / 1463 / 122
Регистрация: 29.05.2011
Сообщений: 3,029
27.07.2011, 23:24 #8
Забавно. Я на n внимания сразу не обратил. В функции, вроде, аргумент скрывает внешнюю переменную? Так что разницы где объявлено n вроде не должно быть. Если, конечно, из файла что-нибудь считывается. Но 0 при глобальной переменной наводит на мысль, что не считывается.
А студия какая?

Добавлено через 1 минуту
Я бы проверил на всякий случай значение n после считывания.
0
ValeryS
Модератор
6729 / 5138 / 484
Регистрация: 14.02.2011
Сообщений: 17,231
27.07.2011, 23:39 #9
Цитата Сообщение от diagon Посмотреть сообщение
Если объявление n перенести в мейн, то выдает 30, если глобально - 0. А правильно будет 3.
глобальные переменные по умолчанию обнуляются локальные нет
явно перекрытие имен
именуй по разному
Цитата Сообщение от diagon Посмотреть сообщение
правильно будет 3.
почему 3
6= 0110 вроде бы два бита =1
0
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
28.07.2011, 09:07  [ТС] #10
Цитата Сообщение от grizlik78 Посмотреть сообщение
В функции, вроде, аргумент скрывает внешнюю переменную?
Должен же.

Цитата Сообщение от grizlik78 Посмотреть сообщение
А студия какая?
2010 ultimate
На acmp VC++ 7.1, также не работает.

Цитата Сообщение от ValeryS Посмотреть сообщение
глобальные переменные по умолчанию обнуляются локальные нет
Так а какая разница, я же считываю в n то, что лежит в файле.

Цитата Сообщение от ValeryS Посмотреть сообщение
почему 3
Ну так
0110 = 110
Реверснутый вариант - 011 = 11 = 3 в десятичной

Добавлено через 23 минуты
Да, там небольшая проблемка со считыванием была.
Однако такой код все равно не работает, как должен
C++
1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <cmath>
int n, k;
int f(int n){
    return n ? f(n/2) + n % 2 * pow(2., k), ++k : 0;
}
int main(){
    std::cin >> n;
    std::cout << f(n) << std::endl;
}
При n == 4 выводит 3, а должен 1.
Здесь важно, чтобы сначала вызывалась f(n/2), а когда n == 0(полностью разложится), то началось вычисляться остальное.
Видимо MSVC вычисляет все за раз =(
0
ForEveR
В астрале
Эксперт С++
7983 / 4742 / 321
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
28.07.2011, 09:30 #11
deleted
1
grizlik78
Эксперт С++
1970 / 1463 / 122
Регистрация: 29.05.2011
Сообщений: 3,029
28.07.2011, 09:37 #12
Цитата Сообщение от diagon Посмотреть сообщение
Видимо MSVC вычисляет все за раз =(
Нет, дело не в этом. Ведь мой "вариант 1" работает корректно?
Дело в операторе запятая
C++
1
2
3
int f(int n){
    return n ? f(n/2) + n % 2 * pow(2., k), ++k : 0;
}
Здесь возвращается не сумма, как того хочется, а увеличенное значение k.

Вариант:
C++
1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <cmath>
int n, k;
int f(int x){
    return x ? n = f(x/2) + x % 2 * pow(2., k), ++k, n : 0;
}
int main(){
        std::cin >> n;
        std::cout << f(n) << std::endl;
}
1
ValeryS
Модератор
6729 / 5138 / 484
Регистрация: 14.02.2011
Сообщений: 17,231
28.07.2011, 10:15 #13
Подсчитал я на бумажке и получается
если в сложении сначала вызывается левая часть( функция )то как ты хочешь
если правая то возвращается то-же что и на входе
тебе надо задать правильный порядок выполнения
например так
C++
1
2
3
4
5
int f(int n){
    if(!n) return 0;
   int tmp= f(n / 2);
    return  tmp + n % 2 * pow(2., k++) ;
}
избався от глобальных переменных
иначе
C++
1
2
3
4
5
int main(){
 int n = 6;
 std::cout << f(n);
 std::cout << f(n);
}
k не обнуляется и при втором вызове будет косяк
теперь по твоей задаче
по твоей логике
1,2,4,8 равно 1
3,6,С равно 3
7 Е равно 7
точно это подразумевалось под словом
Цитата Сообщение от diagon Посмотреть сообщение
развернуть его
может все таки вот так??
0x01= 0x80
0x06= 0x60
эту задачу на микроконтроллере
я решил при помощи таблицы и сдвигов
примерно так
C
1
2
3
4
5
6
7
8
unsigned char tbl[]=
  {0x00, 0x08,0x04,0x0c,0x02,........}
 unsigned char revers(unsigned char n)
  {
  unsigned char tmp1=tbl[(n>>4)&0x0F];
  unsigned char tmp2=tbl[n&0x0F]<<4;
 return tmp1|tmp2;  
 }
1
grizlik78
Эксперт С++
1970 / 1463 / 122
Регистрация: 29.05.2011
Сообщений: 3,029
28.07.2011, 10:21 #14
Кстати о сдвигах.
C++
1
pow(2., k)
видимо правильнее заменить на
C++
1
(1 << k)
0
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
28.07.2011, 10:22  [ТС] #15
Цитата Сообщение от grizlik78 Посмотреть сообщение
Вариант
Wrong Answer 2... Странно.
Вроде все верно...
Цитата Сообщение от ValeryS Посмотреть сообщение
k не обнуляется и при втором вызове будет косяк
Второй вызов не требуется.
Цитата Сообщение от ValeryS Посмотреть сообщение
теперь по твоей задаче
по твоей логике
1,2,4,8 равно 1
3,6,С равно 3
7 Е равно 7
точно это подразумевалось под словом
Точно.
И при чем здесь шестнадцатеричная система счисления, требуются только двоичная и десятичная.
Задача вроде достаточно однозначна, просто не надо ставить нули в начало, как это делали вы с 6.

Цитата Сообщение от grizlik78 Посмотреть сообщение
Кстати о сдвигах.
C++
1
pow(2., k)
видимо правильнее заменить на
C++
1
(1 << k)
Кстати да, тогда не нужно тащить за собой <cmath>, получается значительно короче =)
0
28.07.2011, 10:22
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.07.2011, 10:22
Привет! Вот еще темы с ответами:

Имеются ли отличия в компиляторах у сред разработки Visual Studio 2006 и Visual Studio 2015 ? - C++
скажите а где найти среду 2006 года? или можно использовать 2015 год?

Рекурсия: число различных путей для насекомого из начальной точки поля в конечную - Python
Снова нужна помощь специалистов Представь насекомое на клечатом поле размера M x N . Насекомое стартует из нижнего левого угла (0,...

Есть ли разница в компиляторах? - C (СИ)
на все коды ругается этот компилятор (Borland C++ 3.1). Может там есть какие то свои спец настройки?

Компонент - аналог текстового поля как в компиляторах - C++ Builder
Привет, помню был компонент для борнал делфи 7, аналог текстового поля как в компиляторах. Нумерация строк с лева, возможность выделения,...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.