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

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

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

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

27.07.2011, 22:29. Просмотров 1441. Ответов 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++ этот код неправильно понимает(просто выводит назад это же число).
Собственно, вопрос - что в моей рекурсии неоднозначно? И как ее можно исправить?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.07.2011, 22:29     Рекурсия в различных компиляторах
Посмотрите здесь:

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

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

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

Рекурсия - C++
Сделайте одну програмку используя рекурсию. Очень нужно... Срочно. 1. Реализовать поиск НОД; 2. Возвести число в целую степень; ...

рекурсия в С++ - C++
Изучаю использование рекурсивной функции в С++. Правильно ли я понял: - что нет ограничений в max depth вызова рекурсии которые функция...

Рекурсия - C++
Помогите написать функцию которая будет считать эту рекуррентную формулу с помощью рекурсии

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

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

Добавлено через 1 минуту
Я бы проверил на всякий случай значение n после считывания.
ValeryS
Модератор
6551 / 5017 / 463
Регистрация: 14.02.2011
Сообщений: 16,737
27.07.2011, 23:39     Рекурсия в различных компиляторах #9
Цитата Сообщение от diagon Посмотреть сообщение
Если объявление n перенести в мейн, то выдает 30, если глобально - 0. А правильно будет 3.
глобальные переменные по умолчанию обнуляются локальные нет
явно перекрытие имен
именуй по разному
Цитата Сообщение от diagon Посмотреть сообщение
правильно будет 3.
почему 3
6= 0110 вроде бы два бита =1
diagon
Higher
1928 / 1194 / 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
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
28.07.2011, 09:30     Рекурсия в различных компиляторах #11
deleted
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
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
Модератор
6551 / 5017 / 463
Регистрация: 14.02.2011
Сообщений: 16,737
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
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
28.07.2011, 10:21     Рекурсия в различных компиляторах #14
Кстати о сдвигах.
C++
1
pow(2., k)
видимо правильнее заменить на
C++
1
(1 << k)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.07.2011, 10:22     Рекурсия в различных компиляторах
Еще ссылки по теме:

рекурсия - C++
#include &lt;iostream&gt; #include &lt;windows.h&gt; using namespace std; void someFunction ( int , int, int ); int main () { ...

Рекурсия - C++
#include&lt;stdio.h&gt; void gg(int a,int b) { int i=0; if(a==20) return; printf(&quot;%d\n&quot;,a); printf(&quot;%d\n&quot;,b); gg(a+1,b-1); ...

Рекурсия - C++
Приветствую. Прошу помощи. Нужно посчитать Xn по формуле: С рекурсией плохо дружу. Заранее благодарен.

Рекурсия - C++
Помогите пожалуйста составить программу, с помощью рекурсии: Определить значение отношения максимального и минимального из...

Рекурсия - C++
Сегодня баловался с рекурсией. получилось типа цикла, только из функции #include &lt;iostream&gt; using namespace std; unsigned...


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

Или воспользуйтесь поиском по форуму:
diagon
Higher
1928 / 1194 / 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>, получается значительно короче =)
Yandex
Объявления
28.07.2011, 10:22     Рекурсия в различных компиляторах
Ответ Создать тему
Опции темы

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