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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
27.07.2011, 22:29     Рекурсия в различных компиляторах #1
Доброго времени суток.
Задача: дано целое число 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++ этот код неправильно понимает(просто выводит назад это же число).
Собственно, вопрос - что в моей рекурсии неоднозначно? И как ее можно исправить?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.07.2011, 22:29     Рекурсия в различных компиляторах
Посмотрите здесь:

C++ Рекурсия
Рекурсия C++
C++ рекурсия на с
C++ Рекурсия
C++ Рекурсия C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
27.07.2011, 22:40     Рекурсия в различных компиляторах #2
Цитата Сообщение от diagon Посмотреть сообщение
Собственно, вопрос - что в моей рекурсии неоднозначно?
Порядок вычисления операндов в выражении не определён.
C++
1
f(n / 2) + n % 2 * pow(2., k++)
Видимо в одном случае сначала вычисляется f(n/2) а потом k++, а в другом случае наоборот.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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), ну а дальше остальное выражение, там все однозначно вроде.
У % и * приоритет одинаковый, но % должен первым вычисляться, ибо стоит левее.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
27.07.2011, 22:47     Рекурсия в различных компиляторах #4
у оператора + 2 операнда. Оба являются выражениями, которые надо вычислить перед сложением. Какой из них будет вычислен первым стандартом не оговаривается. В одном случае сначала вычисляется левое выражение, затем правое. В другом сначала правое, потом левое.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
27.07.2011, 22:52  [ТС]     Рекурсия в различных компиляторах #5
Цитата Сообщение от grizlik78 Посмотреть сообщение
у оператора + 2 операнда. Оба являются выражениями, которые надо вычислить перед сложением. Какой из них будет вычислен первым стандартом не оговаривается. В одном случае сначала вычисляется левое выражение, затем правое. В другом сначала правое, потом левое.
Странно как-то... + вообще последним вычисляться должен, у него же наименьший приоритет.
Но даже если так - как тогда это можно исправить? (Минимальным количеством символов, желательно =) ).
Получается, что нужно как-то повысить приоритет у f(n/2)... Но как это сделать - вопрос...
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
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 другим.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
27.07.2011, 23:24     Рекурсия в различных компиляторах #8
Забавно. Я на n внимания сразу не обратил. В функции, вроде, аргумент скрывает внешнюю переменную? Так что разницы где объявлено n вроде не должно быть. Если, конечно, из файла что-нибудь считывается. Но 0 при глобальной переменной наводит на мысль, что не считывается.
А студия какая?

Добавлено через 1 минуту
Я бы проверил на всякий случай значение n после считывания.
ValeryS
Модератор
6375 / 4841 / 443
Регистрация: 14.02.2011
Сообщений: 16,044
27.07.2011, 23:39     Рекурсия в различных компиляторах #9
Цитата Сообщение от diagon Посмотреть сообщение
Если объявление n перенести в мейн, то выдает 30, если глобально - 0. А правильно будет 3.
глобальные переменные по умолчанию обнуляются локальные нет
явно перекрытие имен
именуй по разному
Цитата Сообщение от diagon Посмотреть сообщение
правильно будет 3.
почему 3
6= 0110 вроде бы два бита =1
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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 вычисляет все за раз =(
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
28.07.2011, 09:30     Рекурсия в различных компиляторах #11
deleted
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
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;
}
ValeryS
Модератор
6375 / 4841 / 443
Регистрация: 14.02.2011
Сообщений: 16,044
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;  
 }
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
28.07.2011, 10:21     Рекурсия в различных компиляторах #14
Кстати о сдвигах.
C++
1
pow(2., k)
видимо правильнее заменить на
C++
1
(1 << k)
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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>, получается значительно короче =)
ValeryS
Модератор
6375 / 4841 / 443
Регистрация: 14.02.2011
Сообщений: 16,044
28.07.2011, 10:26     Рекурсия в различных компиляторах #16
все дело в k
про одном варианте он 0,1,2(то же число)
при другом 2,1,0 (реверс)
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
28.07.2011, 10:28  [ТС]     Рекурсия в различных компиляторах #17
Таки нет. Прошла все тесты, когда сменил pow на 1 << k.
Всем спасибо.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
28.07.2011, 10:31     Рекурсия в различных компиляторах #18
Цитата Сообщение от diagon Посмотреть сообщение
Таки нет. Прошла все тесты, когда сменил pow на 1 << k.
Я недавно пытался получить ошибку округления в pow на GCC. Не получилось. Но я всегда верил, что она возможна!
Спасибо.
ValeryS
Модератор
6375 / 4841 / 443
Регистрация: 14.02.2011
Сообщений: 16,044
28.07.2011, 10:31     Рекурсия в различных компиляторах #19
Цитата Сообщение от diagon Посмотреть сообщение
И при чем здесь шестнадцатеричная система счисления, требуются только двоичная и десятичная.
а ниче что в памяти они все двоичные ???

Цитата Сообщение от diagon Посмотреть сообщение
Задача вроде достаточно однозначна, просто не надо ставить нули в начало, как это делали вы с 6.
а в процессоре ты тоже запретишь лишние разряды???
Цитата Сообщение от diagon Посмотреть сообщение
Второй вызов не требуется.
кому не требуется ???
если мне надо перевести 20 чисел я должен писать 20 программ?
и где нужна такая задача?
что
Цитата Сообщение от ValeryS Посмотреть сообщение
1,2,4,8 равно 1
3,6,С равно 3
7 Е равно 7
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.07.2011, 10:34     Рекурсия в различных компиляторах
Еще ссылки по теме:

рекурсия C++
Работает в онлайн компиляторах, но не работает у меня C++
Количество различных цифр в числе рекурсия C++

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

Или воспользуйтесь поиском по форуму:
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
28.07.2011, 10:34     Рекурсия в различных компиляторах #20
Цитата Сообщение от ValeryS Посмотреть сообщение
если мне надо перевести 20 чисел я должен писать 20 программ?
Достаточно перед вызовом обнулять k вручную
Но задача специфическая. В первом сообщении сказано, что решение есть, вопрос был только про рекурсию.
Yandex
Объявления
28.07.2011, 10:34     Рекурсия в различных компиляторах
Ответ Создать тему
Опции темы

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