Từ 1 tới 4 trên tổng số 4 kết quả

Đề tài: chương trình đổi 1 số nguyên trong hệ thập phân sang hệ fibo và cộng 2 số nguyên được

  1. #1
    Ngày gia nhập
    01 2011
    Bài viết
    1

    Mặc định chương trình đổi 1 số nguyên trong hệ thập phân sang hệ fibo và cộng 2 số nguyên được

    Dãy Fibonacy được định nghĩa như sau:
    • F0 = 1
    • F1 = 2
    • Fi = Fi-1 + Fi-2
    Vài phần tử đầu tiên của dãy được cho dưới đây:
    1 2 3 5 8 13 21 34 55 89 144 …
    Một điều thú vị là mọi số nguyên dương bất kỳ điều có thể biểu diễn bằng tổng các số
    Fibonacy khác nhau. Ví dụ: 13 có thể biểu diễn bằng{13}, {5, 8} hay {2, 3, 8}; 17 có thể
    biểu diễn bằng {1, 3, 13} hay {1, 3, 5, 8}. Tất cả các số nguyên dương đều có tính chất này
    (bạn có muốn tự mình chứng minh không ?). Vì thế ta có thể sử dụng các số Fibonacy như là
    “cơ số” để biểu diễn các số nguyên. Tuy nhiên, như ta đã thấy một số có thể có nhiều cách
    biểu diễn. Vậy làm thế nào để mỗi số chỉ có duy nhất một cách biểu diễn. Cách đơn giản là
    thêm vào ràng buộc: “không sử dụng 2 số Fibonacy liên tiếp nhau để biểu diễn”.
    Như thế là có một cách rất thú vị để biểu diễn các số nguyên thay vì dùng cơ số 2, cơ số 10,
    hay cơ số 16, …
    Ví dụ: 17 = 1 + 3 + 13, được biểu diễn dưới dạng chuỗi 0, 1 như sau:
    17 = 1 0 0 1 0 1
    13+3+1 = 13 8 5 3 2 1
    Nói cách khác 17(10) = 100101(fibo)
    Yêu cầu:
    a. Viết chương trình đổi 1 số nguyên trong hệ thập phân sang hệ fibo
    Ví dụ:
    Đầu vào Kết quả
    1 1 = 1 (fibo)
    2 2 = 10 (fibo)
    3 3 = 100 (fibo)
    4 4 = 101(fibo)
    5 5 = 1000 (fibo)
    6 6 = 1001 (fibo)
    7 7 = 1010 (fibo)
    b. Viết chương trình cộng 2 số nguyên được biểu diễn trong hệ fibo (chú ý: các số này có
    thể rất dài)
    Ví dụ: 100 (fibo) + 1010 (fibo) = 10010 (fibo)

    Em rất cám ơn anh chị nào giúp đỡ !
    Sửa/Xóa bài viết

  2. #2
    Ngày gia nhập
    09 2010
    Bài viết
    207

    Câu A

    C++ Code:
    1. // LearnCpp.cpp : Defines the entry point for the console application.
    2. //
    3.  
    4. #include "stdafx.h"
    5. #include <iostream>
    6. using namespace std;
    7.  
    8. void GenFiboBase(int base[], const int max)
    9. {
    10.     base[0] = 1;
    11.     base[1] = 2;
    12.     for(int i=2; i<max; i++)
    13.         base[i] = base[i-1] + base[i-2];
    14. }
    15.  
    16. bool convert(const int value, const int base[], const int limit, int Fibo[])
    17. {
    18.     int i;
    19.     for(i=0; i<limit && base[i]<=value; i++)
    20.         ;
    21.  
    22.     while(--i>=0)
    23.     {
    24.         // Try
    25.         Fibo[i] = 1;
    26.         int mod = value % base[i];
    27.         if(mod == 0)
    28.             return true;
    29.         if(convert(mod, base, i-1, Fibo))
    30.             return true;
    31.  
    32.         Fibo[i] = 0;
    33.     }
    34.     return false;
    35. }
    36.  
    37. void convert(int value, char FiboString[])
    38. {
    39.     int base[100], max = 100, Fibo[100], n = 0;
    40.     for(int i=0; i<max; i++)
    41.         Fibo[i] = 0;
    42.  
    43.     GenFiboBase(base, max);
    44.     convert(value, base, max, Fibo);
    45.  
    46.     for(n=max-1; n>0 && Fibo[n] == 0; n--);
    47.  
    48.     FiboString[n+1] = 0;
    49.     for(int i=0; n>=0; i++, n--)
    50.         FiboString[i] = Fibo[n] + '0';
    51. }
    52.  
    53. int main()
    54. {
    55.     char str[100];
    56.     for(int i=1; i<20; i++)
    57.     {
    58.         convert(i, str);
    59.         cout << i << "\t" << str << endl;
    60.     }
    61.     system("pause");
    62.     return 0;
    }
    C++ Code:
    1. while ( ! Love(I, You) )
    2.     try { Send(I, You, ..... ); .....; } catch (LoveException lvex) { fix_error(); }
    3. Marry ( I, You );
    4. while ( true )
    5.     try { ....together; } catch (Exception ex) { remove_bad_things(); }

  3. #3
    Ngày gia nhập
    03 2010
    Bài viết
    47

    C Code:
    1. #include <stdio.h>
    2.  
    3. typedef signed   long int s_int32;
    4. typedef unsigned long int u_int32;
    5. typedef unsigned long long int u_int64;
    6. typedef unsigned long long int intFibb;
    7.  
    8. #define MAX_FIBB 46
    9. u_int32 Fibb(u_int32 n)
    10. {
    11.     static const u_int32 lookup[MAX_FIBB] =
    12.         {1,         2,          3,          5,          8,          // 0  - 4
    13.          13,        21,         34,         55,         89,         // 5  - 9
    14.          144,       233,        377,        610,        987,        // 10 - 14
    15.          1597,      2584,       4181,       6765,       10946,      // 15 - 19
    16.          17711,     28657,      46368,      75025,      121393,     // 20 - 24
    17.          196418,    317811,     514229,     832040,     1346269,    // 25 - 29
    18.          2178309,   3524578,    5702887,    9227465,    14930352,   // 30 - 34
    19.          24157817,  39088169,   63245986,   102334155,  165580141,  // 35 - 39
    20.          267914296, 433494437,  701408733,  1134903170, 1836311903, // 40 - 44
    21.          2971215073};                                               // 45
    22.          
    23.     if (n < MAX_FIBB)
    24.         return lookup[n];
    25.     else return 0;
    26. }
    27.  
    28. intFibb encodeFibb(u_int32 n)
    29. {
    30.     s_int32 ii;
    31.     intFibb result = 0;
    32.    
    33.     for (ii = MAX_FIBB-1; ii >=0; ii--, result <<= 1)
    34.         if (n >= Fibb(ii))
    35.         {
    36.             result++;
    37.             n -= Fibb(ii);
    38.         }      
    39.    
    40.     return result>>1;
    41. }
    42.  
    43. u_int32 decodeFibb(intFibb n)
    44. {
    45.     s_int32 ii;
    46.     u_int32 result = 0;
    47.    
    48.     for (ii = 0; ii < MAX_FIBB; ii++, n >>= 1)
    49.         if(n & 0x00000001)
    50.             result += Fibb(ii);
    51.    
    52.     return result;
    53. }
    54.  
    55. intFibb normalFib(u_int64 n)
    56. {
    57.     s_int32 ii = 0;
    58.     u_int64 window  = 0x07,  // b111 we want to look at 3 consecutive num
    59.             compare = 0x03,  // b011 then compare it with 011
    60.             incr    = 0x01;  // b001 if ok, add incr to it to get b100
    61.     while(ii<MAX_FIBB)
    62.     {
    63.         if (compare == (n&window))
    64.         {
    65.             // detected; let's add incr to n
    66.             n += incr;
    67.             // restart the process
    68.             ii = 0; window = 0x07; compare = 0x03; incr = 0x01;
    69.         }
    70.         else
    71.         {
    72.             // not detected; move forward
    73.             ii++; window <<=1; compare <<=1; incr<<=1;
    74.         }
    75.     }
    76.     return n;
    77. }
    78.  
    79. intFibb addFibb(intFibb a, intFibb b)
    80. {
    81.     return encodeFibb(decodeFibb(a) + decodeFibb(b));
    82. }
    83.  
    84. intFibb addFibb2(intFibb a, intFibb b)
    85. {
    86.     intFibb n = a + b;
    87.     return normalFib(n);
    88. }
    89.  
    90. #undef MAX_FIBB
    91.  
    92. u_int32 printBin(const u_int64 n)
    93. {
    94.     char c;
    95.     s_int32 ii, count = 0, zerotrail = 1;
    96.     u_int64 mask = 0x8000000000000000;
    97.  
    98.     for(ii=0; ii<sizeof(u_int64)*8; ii++, mask>>=1)
    99.     {
    100.         c = (n & mask) ? '1' : '0';
    101.         if ((zerotrail) && c =='1')
    102.             zerotrail = 1;
    103.         if (!zerotrail)
    104.         {
    105.             if (c!=putchar(c))
    106.                 return -1;
    107.             count++;
    108.         }
    109.     }
    110.     return count;
    111. }
    112.  
    113. int main()
    114. {
    115.     u_int32 x = 25, y= 49;
    116.     intFibb result1, result2, resultAdd1, resultAdd2;
    117.    
    118.     result1 = encodeFibb(x);
    119.     result2 = encodeFibb(y);
    120.  
    121.     resultAdd1 = addFibb(result1, result2);
    122.     resultAdd2 = addFibb2(result1, result2);
    123.  
    124.     printf("The number %d in Fibbonacci code is: ", x);
    125.     printBin(result1); printf("\n");
    126.  
    127.     printf("The number %d in Fibbonacci code is: ", y);
    128.     printBin(result2); printf("\n");
    129.  
    130.     printf("The sum of them in decimal is: %d\n", x + y);
    131.     printf("The sum of them in binary is: ");
    132.     printBin(x+y); printf("\n");
    133.     printf("The sum of them in Fibbonacci code (method 1: convert back to int,\n");
    134.     printf("perform adding in decimal then convert back) is: ");
    135.     printBin(resultAdd1); printf("\n");
    136.    
    137.     printf("The sum of them in Fibbonacci code (method 2: add the numbers, then\n");
    138.     printf("normalize the result) is: ");
    139.     printBin(resultAdd2); printf("\n");
    140.     return 0;
    141. }

    Code viết nhanh nên chưa test nhiều ._."

  4. #4
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    C++ version:
    Make sure you have boost-bimap installed & C++0x.

    C++ Code:
    1. #include <iostream>
    2. #include <string>
    3. #include <bitset>
    4. #include <map>
    5. #include <vector>
    6. #include <set>
    7. #include <functional>
    8. #include <numeric>
    9. #include <algorithm>
    10.  
    11. #include <boost/bimap.hpp>
    12.  
    13. using namespace std;
    14. using namespace boost;
    15.  
    16. typedef unsigned __int64 u64;
    17. typedef boost::bimap<u64, unsigned> fibmap_type;
    18. typedef fibmap_type::value_type fm_pair;
    19.  
    20. template<u64 n>
    21. struct fib {
    22.     enum { value = fib<n - 1>::value + fib<n - 2>::value };
    23.     static void insert( fibmap_type& fm ) {
    24.         fib<n - 1>::insert( fm );
    25.         fm.insert( fm_pair( value, n ) );
    26.     };
    27. };
    28.  
    29. template<>
    30. struct fib<1> {
    31.     enum { value = 1 };
    32.     static void insert( fibmap_type& fm ) {
    33.         fm.insert( fm_pair( value, 1 ) );
    34.     };
    35. };
    36.  
    37. template<>
    38. struct fib<0> {
    39.     enum { value = 1 };
    40.     static void insert( fibmap_type& fm ) {
    41.         fm.insert( fm_pair( value, 0 ) );
    42.     };
    43. };
    44.  
    45. class fibonacci_binary {
    46. public:
    47.     fibonacci_binary( const u64& value ) : value( value ) {
    48.         fib<50>::insert( fm );
    49.         value_str = to_string( value );
    50.     }
    51.  
    52.     fibonacci_binary( const string& value_str ) : value_str( value_str ) {
    53.         fib<50>::insert( fm );
    54.         value = to_fib( value_str );
    55.     }
    56.  
    57.     fibonacci_binary( const char* value_str ) {
    58.         fib<50>::insert( fm );
    59.         this->value_str = value_str;
    60.         this->value = to_fib( this->value_str );
    61.     }
    62.  
    63.     operator u64() const {
    64.         return value;
    65.     }
    66.  
    67.     operator string() const {
    68.         return value_str;
    69.     }
    70.  
    71.     fibonacci_binary& operator =( const u64& value ) {
    72.         this->value = value;
    73.         value_str = to_string( this->value );
    74.         return *this;
    75.     }
    76.  
    77.     fibonacci_binary& operator =( const string& value_str ) {
    78.         this->value_str = value_str;
    79.         value = to_fib( this->value_str );
    80.         return *this;
    81.     }
    82.  
    83.     bool operator ==( const fibonacci_binary& rhs ) const {
    84.         return value == rhs.value;
    85.     }
    86.  
    87.     bool operator !=( const fibonacci_binary& rhs ) const {
    88.         return value != rhs.value;
    89.     }
    90.  
    91.     fibonacci_binary operator +( const fibonacci_binary& rhs ) const {
    92.         return fibonacci_binary( value + rhs.value );
    93.     }
    94.  
    95.     fibonacci_binary& operator +=( const fibonacci_binary& rhs ) {
    96.         *this = *this + rhs;
    97.         return *this;
    98.     }
    99.  
    100. public:
    101.     friend
    102.     ostream& operator <<( ostream& out, const fibonacci_binary& rhs ) {
    103.         return out << rhs.value << ", " << rhs.value_str;
    104.     }
    105.  
    106. private:
    107.     string to_string( u64 n ) const {
    108.         set<unsigned, greater<unsigned>> pos( get_positions( n ) );
    109.         string res( *pos.begin(), '0' );
    110.         for( auto it = pos.begin(); it != pos.end(); ++it ) {
    111.             res[*it - 1] = '1';
    112.         }  
    113.         return string( res.rbegin(), res.rend() );
    114.     }
    115.  
    116.     u64 to_fib( const string& fstr ) const {
    117.         string rstr( fstr.rbegin(), fstr.rend() ); 
    118.         u64 result( 0 );
    119.         for( unsigned i = 0, len = rstr.length(); i < len; ++i ) {
    120.             if( rstr[i] == '1' ) {
    121.                 auto iter = fm.right.find( i + 1 );
    122.                 if( iter != fm.right.end() ) {
    123.                     result += iter->second;
    124.                 }
    125.             }
    126.         }
    127.         return result;
    128.     }
    129.  
    130.     set<unsigned, greater<unsigned>> get_positions( u64 n ) const {
    131.         set<unsigned, greater<unsigned>> pos; // position vector
    132.         auto it = fm.left.find( n );
    133.         if( it != fm.left.end() ) {
    134.             pos.insert( it->second );
    135.         }
    136.         else {
    137.             while( n ) {
    138.                 auto at = fm.left.upper_bound( n );
    139.                 at--;
    140.                 pos.insert( at->second );
    141.                 n -= at->first;
    142.             }
    143.         }
    144.         return pos;
    145.     }
    146.  
    147. private:
    148.     fibmap_type fm;
    149.     u64 value;
    150.     string value_str;
    151. };
    152.  
    153. int main() {
    154.     // simple test 1
    155.     fibonacci_binary fb1( "100101" );
    156.     fb1 += 3;
    157.     cout << "fb1 = " << fb1 << endl;
    158.     // simple test 2
    159.     fibonacci_binary fb2( 7 );
    160.     cout << "fb2 = " << fb2 << endl;
    161.     string bin_str = fb2;
    162.     cout << "bin_str = " << bin_str << endl;
    163.     return 0;
    164. }

Các đề tài tương tự

  1. Chuyển một số nguyên hệ 10 sang hệ 2 ????
    Gửi bởi falcao123 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 18
    Bài viết cuối: 24-07-2013, 09:22 PM
  2. Kỹ thuật C++ Đổi số nguyên không âm sang dạng nhị phân
    Gửi bởi ngoclong93 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 24-06-2013, 04:07 PM
  3. Kiểm tra xem trong mảng các số nguyên có tồn tại số nguyên lẻ hayko?
    Gửi bởi caphetim trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 8
    Bài viết cuối: 06-05-2013, 03:56 PM
  4. Database cách nhập nhiều nguyên liệu cho một món ăn trong một form quản lý nguyên liệu món ăn
    Gửi bởi mamachue92 trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 1
    Bài viết cuối: 31-10-2012, 09:55 AM
  5. tìm số nguyên tố có trong mảng 2 chiều, tính tổng các số nguyên tố đó??
    Gửi bởi lesliuton01 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 8
    Bài viết cuối: 08-06-2010, 10:21 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn