Решение задачи Система счисления Фибоначчи с Acmp

Без пояснения   Просмотров: 63


Числа Фибоначчи F1, F2, … определяются начальными значениями и соотношением:

F1=1; F2=2; Fn=Fn-1+Fn-2.

Рассмотрим систему счисления с двумя цифрами 0 и 1, в которой, в отличие от двоичной системы, весами являются не степени двойки 1, 2, 4, 8, 16, …, а числа Фибоначчи 1, 2, 3, 5, 8, 13, …. В этой системе счисления каждое положительное целое число единственном способом представляется в виде строки из нулей и единиц, которая начинается с 1 и в которой нет двух единиц, стоящих рядом.

Требуется написать программу, которая по двум заданным строкам, представляющим числа A и B в системе счисления Фибоначчи, находила строку, представляющую число A+B также в этой системе счисления.

Например, исходные строки 10101 и 100 представляют числа 1*8+0*5+1*3+0*2+1*1=8+3+1=12 и 1*3+0*2+0*1=3. Ответом является строка 100010, представляющая число 1*13+0*8+0*5+0*3+1*2+0*1=13+2=15=12+3.

Код

#include <bits/stdc++.h>
 
using namespace std;
 
string func(string s,string s1)
{
    string sum = "";
    if(s.size() < s1.size())
        return func(s1,s);
    if(s.size() > s1.size())
        s1.insert(0, s.size() - s1.size(), '0');
    for(int i = 0; i < s.size(); ++i)
        sum.push_back(s[i] + s1[i] - 48);
    return sum;
}
int main()
{
    string s,s1;
    cin >> s >> s1;
    string sum = func(s,s1);
    sum.insert(0,10, '0');
    int pos = sum.find("011");
    while(pos + 1){
        sum.replace(pos,3,"100");
        pos = sum.find("011");
    }
    if(sum[sum.size() - 1] == '2'){
        sum[sum.size() - 2]++;
        sum[sum.size() - 1] = '0';
    }
    if(sum[sum.size() - 2] == '2'){
        sum[sum.size() - 1]++;
        sum[sum.size() - 3]++;
        sum[sum.size() - 2] = '0';
    }
    int pos1 = sum.rfind('2');
    while(pos1 + 1){
        sum[pos1 + 2]++;
        sum[pos1 - 1]++;
        sum[pos1] = '0';
        pos1 = sum.rfind('2');
    }
 
    pos = sum.find("011");
    while(pos + 1){
        sum.replace(pos,3,"100");
        pos = sum.find("011");
    }
    while(sum[0] == '0'){
        sum.erase(0,1);
    }
    cout << sum;
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться