Форум программистов, компьютерный форум 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++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
28.07.2011, 10:41  [ТС]     Рекурсия в различных компиляторах #21
Цитата Сообщение от ValeryS Посмотреть сообщение
а ниче что в памяти они все двоичные ???
Так вы на условие задачи посмотрите. Здесь более точный вариант условия. Перегнать число из десятичной в двоичную СС и обратно ничего не стоит, хекс здесь лишний.

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


Цитата Сообщение от ValeryS Посмотреть сообщение
если мне надо перевести 20 чисел я должен писать 20 программ?
Одну, но хорошую =)
Передо мной стояла задача не написать универсальную и читабельную программу, а решить простенькую задачу минимальным количеством символов. Среди цппшников я, в общем-то, первый.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,043
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 Посмотреть сообщение
Перегнать число из десятичной в двоичную СС и обратно ничего не стоит
что значит перегнать???
вывести на экран(принтер)?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
28.07.2011, 10:47  [ТС]     Рекурсия в различных компиляторах #23
Цитата Сообщение от ValeryS Посмотреть сообщение
что значит перегнать
Получить массив нуликов/еденичек, который и нужно реверснуть, а потом реверснутый вариант перегнать обратно в десятичную СС.
Но со стеком рекурсии более красивое и короткое решение получается.
ValeryLaptev
Эксперт C++
1004 / 783 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
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()
Попробуйте без глобальных переменных - это гораздо интереснее...
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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 символа короче =(
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
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;
}
Миниатюры
Рекурсия в различных компиляторах  
ValeryLaptev
Эксперт C++
1004 / 783 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
29.07.2011, 09:43     Рекурсия в различных компиляторах #27
easybudda, да. Это хороший подход - реверсить строку битов.
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 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;
ValeryLaptev
Эксперт C++
1004 / 783 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
29.07.2011, 12:51     Рекурсия в различных компиляторах #29
fasked, здесь предполагается, что размер целого равен 32 битам, 4 байтам. Это не везде так... При изменени размеров целого придется дописывать функцию. А в рекурсивной версии - нет.
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
29.07.2011, 13:19     Рекурсия в различных компиляторах #30
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
здесь предполагается, что размер целого равен 32 битам, 4 байтам. Это не везде так... При изменени размеров целого придется дописывать функцию. А в рекурсивной версии - нет.
Это да, но я не могу представить себе программы, где приходится заниматься реверсом битов и в которой заранее нет четкого представления о настолько низком уровне. То есть задача явно либо олимпиадная, либо для программирования каких-нибудь железяк, а уж там то все строго. Ну и конечно скорость и потребление памяти по сравнению с рекурсией.
То есть за все надо платить
ValeryLaptev
Эксперт C++
1004 / 783 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
29.07.2011, 13:22     Рекурсия в различных компиляторах #31
fasked, не... Вспомните big-endian и little-endian.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.07.2011, 13:38     Рекурсия в различных компиляторах
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
29.07.2011, 13:38     Рекурсия в различных компиляторах #32
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Вспомните big-endian и little-endian.
Ну а разве это не низкий уровень? Есть четкая документация, как работает железка или спецификация протокола. Все следуют подобной документации и ... я не думаю, что возможны какие-либо значительные изменения в будущем, а введение дополнительного слоя абстракции легко позволит избежать проблем при появлении незначительных изменений.
Yandex
Объявления
29.07.2011, 13:38     Рекурсия в различных компиляторах
Ответ Создать тему
Опции темы

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