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

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

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

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

27.07.2011, 22:29. Просмотров 1456. Ответов 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; ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
ValeryS
Модератор
6631 / 5038 / 466
Регистрация: 14.02.2011
Сообщений: 16,848
28.07.2011, 10:26 #16
все дело в k
про одном варианте он 0,1,2(то же число)
при другом 2,1,0 (реверс)
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
28.07.2011, 10:28  [ТС] #17
Таки нет. Прошла все тесты, когда сменил pow на 1 << k.
Всем спасибо.
1
grizlik78
Эксперт С++
1911 / 1443 / 112
Регистрация: 29.05.2011
Сообщений: 3,000
28.07.2011, 10:31 #18
Цитата Сообщение от diagon Посмотреть сообщение
Таки нет. Прошла все тесты, когда сменил pow на 1 << k.
Я недавно пытался получить ошибку округления в pow на GCC. Не получилось. Но я всегда верил, что она возможна!
Спасибо.
0
ValeryS
Модератор
6631 / 5038 / 466
Регистрация: 14.02.2011
Сообщений: 16,848
28.07.2011, 10:31 #19
Цитата Сообщение от diagon Посмотреть сообщение
И при чем здесь шестнадцатеричная система счисления, требуются только двоичная и десятичная.
а ниче что в памяти они все двоичные ???

Цитата Сообщение от diagon Посмотреть сообщение
Задача вроде достаточно однозначна, просто не надо ставить нули в начало, как это делали вы с 6.
а в процессоре ты тоже запретишь лишние разряды???
Цитата Сообщение от diagon Посмотреть сообщение
Второй вызов не требуется.
кому не требуется ???
если мне надо перевести 20 чисел я должен писать 20 программ?
и где нужна такая задача?
что
Цитата Сообщение от ValeryS Посмотреть сообщение
1,2,4,8 равно 1
3,6,С равно 3
7 Е равно 7
0
grizlik78
Эксперт С++
1911 / 1443 / 112
Регистрация: 29.05.2011
Сообщений: 3,000
28.07.2011, 10:34 #20
Цитата Сообщение от ValeryS Посмотреть сообщение
если мне надо перевести 20 чисел я должен писать 20 программ?
Достаточно перед вызовом обнулять k вручную
Но задача специфическая. В первом сообщении сказано, что решение есть, вопрос был только про рекурсию.
1
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
28.07.2011, 10:41  [ТС] #21
Цитата Сообщение от ValeryS Посмотреть сообщение
а ниче что в памяти они все двоичные ???
Так вы на условие задачи посмотрите. Здесь более точный вариант условия. Перегнать число из десятичной в двоичную СС и обратно ничего не стоит, хекс здесь лишний.

Цитата Сообщение от ValeryS Посмотреть сообщение
а в процессоре ты тоже запретишь лишние разряды???
А при чем здесь процессор? Двоичную СС не только в нем можно использовать =)


Цитата Сообщение от ValeryS Посмотреть сообщение
если мне надо перевести 20 чисел я должен писать 20 программ?
Одну, но хорошую =)
Передо мной стояла задача не написать универсальную и читабельную программу, а решить простенькую задачу минимальным количеством символов. Среди цппшников я, в общем-то, первый.
0
ValeryS
Модератор
6631 / 5038 / 466
Регистрация: 14.02.2011
Сообщений: 16,848
28.07.2011, 10:44 #22
Цитата Сообщение от grizlik78 Посмотреть сообщение
Но задача специфическая.
для переворота байта (слова ) достаточно распространенная удивляюсь что в стандартные библиотеки не встроили (или где то есть)?
но в таком варианте

Цитата Сообщение от diagon Посмотреть сообщение
0110 = 110
Реверснутый вариант - 011 = 11 = 3 в десятичной
потому получается
Цитата Сообщение от ValeryS Посмотреть сообщение
1,2,4,8 равно 1
3,6,С равно 3
7 Е равно 7
взял полубайты (вообше ответов куда больше)
я не знаю где она может пригодится

Добавлено через 2 минуты
Цитата Сообщение от diagon Посмотреть сообщение
Перегнать число из десятичной в двоичную СС и обратно ничего не стоит
что значит перегнать???
вывести на экран(принтер)?
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
28.07.2011, 10:47  [ТС] #23
Цитата Сообщение от ValeryS Посмотреть сообщение
что значит перегнать
Получить массив нуликов/еденичек, который и нужно реверснуть, а потом реверснутый вариант перегнать обратно в десятичную СС.
Но со стеком рекурсии более красивое и короткое решение получается.
0
ValeryLaptev
Эксперт С++
1041 / 820 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
28.07.2011, 15:50 #24
При использовании глобальных переменных все гораздо проще получается:
C++
1
2
3
4
5
6
7
8
9
10
int k = 0;
 
int f(int d)
{ int b = d % 2;
  if(d > 0)
  { k = (k * 2 + b);
    int r = f(d/2); 
  }
  return k;   
}
И никаких pow()
Попробуйте без глобальных переменных - это гораздо интереснее...
1
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
28.07.2011, 15:55  [ТС] #25
Можно еще проще(ну во всяком случае короче):
C++
1
2
3
4
int n, k;
int f(int n){
    return n ? f(n / 2) + n % 2 * (1 << k++) : 0;
}
У паскалистов на 4 символа короче =(
0
easybudda
Модератор
Эксперт CЭксперт С++
9625 / 5573 / 947
Регистрация: 25.07.2009
Сообщений: 10,708
29.07.2011, 00:25 #26
Не уверен, что правильно понял, но вот чего набыдлокодил...
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
31
32
33
34
#include <stdio.h>
#include <limits.h>
 
#define INT_BITS (CHAR_BIT * sizeof(int))
 
void bindump(unsigned val){
    int i = INT_BITS;
    
    while ( i )
        printf("%d", (val >> --i) & 1);
    printf("\n");
}
 
unsigned bit_reverse(unsigned val, size_t pos){
    return ( pos > 1 ) ? (bit_reverse(val, pos - 1) << 1) | ((val >> (pos - 1)) & 1) : val & 1;
}
 
int num_reverse(int num){
    return (int)bit_reverse((unsigned)num, INT_BITS);
}
 
int main(void){
    int num, rev;
    
    while ( printf("Number: ") && scanf("%d", &num) == 1 ){
        printf("DEC: %11d\tBIN: ", num);
        bindump(num);
        rev = num_reverse(num);
        printf("DEC: %11d\tBIN: ", rev);
        bindump(rev);
    }
    
    return 0;
}
2
Миниатюры
Рекурсия в различных компиляторах  
ValeryLaptev
Эксперт С++
1041 / 820 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
29.07.2011, 09:43 #27
easybudda, да. Это хороший подход - реверсить строку битов.
0
fasked
Эксперт С++
4936 / 2516 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
29.07.2011, 12:22 #28
Рекурсия это конечно здорово, но сам реверс битов делается вот так:
C
1
2
3
4
5
6
unsigned bitrev(unsigned x) {
   x = (x & 0x55555555) <<  1 | (x >>  1) & 0x55555555; 
   x = (x & 0x33333333) <<  2 | (x >>  2) & 0x33333333; 
   x = (x & 0x0F0F0F0F) <<  4 | (x >>  4) & 0x0F0F0F0F; 
   x = (x << 24) | ((x & 0xFF00) << 8) | ((x >> 8) & 0xFF00) | (x >> 24); 
   return x;
1
ValeryLaptev
Эксперт С++
1041 / 820 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
29.07.2011, 12:51 #29
fasked, здесь предполагается, что размер целого равен 32 битам, 4 байтам. Это не везде так... При изменени размеров целого придется дописывать функцию. А в рекурсивной версии - нет.
0
fasked
Эксперт С++
4936 / 2516 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
29.07.2011, 13:19 #30
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
здесь предполагается, что размер целого равен 32 битам, 4 байтам. Это не везде так... При изменени размеров целого придется дописывать функцию. А в рекурсивной версии - нет.
Это да, но я не могу представить себе программы, где приходится заниматься реверсом битов и в которой заранее нет четкого представления о настолько низком уровне. То есть задача явно либо олимпиадная, либо для программирования каких-нибудь железяк, а уж там то все строго. Ну и конечно скорость и потребление памяти по сравнению с рекурсией.
То есть за все надо платить
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.07.2011, 13:19
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
29.07.2011, 13:19
Ответ Создать тему
Опции темы

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