Как выглядит программа кодирования исходного числа кодом Фибоначчи?

A_i_n_u_r

Как выглядит программа кодирования исходного числа кодом Фибоначчи? Если известно, что натуральное число определяется следующим образом: если в сумме присутствует число Фибоначчи с номером , то в соответствующей позиции, начиная справа, ставится единица; если число Фибоначчи с номером отсутствует в сумме, в соответствующей позиции ставится ноль, например: 7 = 10100, 20 = 1010100, 33 = 10101010. И какой вид имеет число 45274? Очень надо, помогите пожалуйста...
2 ответа

A_i_n_u_r

Вы, по-моему немного неверно описываете код Фибоначчи. http://en.wikipedia.org/wiki/Fibonacci_coding Функция fibm - не моя, не помню откуда взял, но работает хорошо. Ну и, вероятно, можно немного оптимизировать, но мне лень.
namespace fib
{
    static class Program
    {
        /// <summary>
        /// Главная точка входа для приложения.
        /// </summary>
        [STAThread]
        static void Main()
        {
            int n=45274;
            
            
            int i = 1;
            for (i=1; fibm(i)<=n;i++)
            {
                
            }
            i--;
            string r = "1";
            for (int j=i;j>1;j--)
            {
                int t=fibm(j);
                if (n >= t)
                {
                    n -= t;
                    r = "1" + r;
                }
                else
                {
                    r = "0" + r;
                }
            }
 
 
            MessageBox.Show(r);
        }
 
 
        public struct mtx2x2
        {
            public int _11, _12, _21, _22;
            public static mtx2x2 operator *(mtx2x2 lhs, mtx2x2 rhs)
            {
                return new mtx2x2
                {
                    _11 = lhs._11 * rhs._11 + lhs._12 * rhs._21,
                    _12 = lhs._11 * rhs._12 + lhs._12 * rhs._22,
                    _21 = lhs._21 * rhs._11 + lhs._22 * rhs._21,
                    _22 = lhs._21 * rhs._12 + lhs._22 * rhs._22
                };
            }
        }
 
        private static readonly mtx2x2 fibMtx = new mtx2x2 { _11 = 1, _12 = 1, _21 = 1 };
        private static readonly mtx2x2 identity = new mtx2x2 { _11 = 1, _22 = 1 };
 
        public static mtx2x2 IntPower(mtx2x2 x, short power)
        {
            if (power == 0) return identity;
            if (power == 1) return x;
            int n = 15;
            while ((power <<= 1) >= 0) n--;
            mtx2x2 tmp = x;
            while (--n > 0)
                tmp = (tmp * tmp) * (((power <<= 1) < 0) ? x : identity);
            return tmp;
        }
 
 
        static int fibm(int n)
        {
            return IntPower(fibMtx, (short)(n - 1))._11;
        }
 
 
        
    }
}


A_i_n_u_r

namespace Test_Fib
{
    class Fibonachi
    {      
        static void Main(string[] args)
        {
            Console.Write("Введите N: ");//Выводим на экран строку "Введите N:"
            int N = Convert.ToInt16(Console.ReadLine());//Объявляем целочисленную переменну "N" и считываем введенное число и меняем его тип данных на целочисленный.
            int f = 0;//Объявление целочисленной переменной "f" с значением "0"
            int f1 = 1;//Объявление целочисленной переменной "f1" с значением "1"
            int f2 = 1;//Объявление целочисленной переменной "f2" с значением "1"
            int i = 0;//Объявление целочисленной переменной "i" с значением "0"
            bool ok = false;//Объявление логической переменной "ok" с значением "false"
            int pos = 0;//Объявление целочисленной переменной "pos" с значением "0"
            while (f2 < N)//Цикл while с условием, что пока значение пременной "f2" меньше значения пременной 
            {
                Console.WriteLine(f2);//Выводим на экран значение переменной "f2"
                f2 = f1 + f;//Переменной "f2" присваиваем значение суммы 
                f = f1;//Переменной "f" присваиваем значение переменной "f1"
                f1 = f2;//Переменной "f1" присваиваем значение переменной "f2"
                i++;//Увеличиваем значение переменной(счетчик) "i" на единицу
                if (f2 == N)//Создаем условие, чтобы проверить не превысило ли значение введенного числа, значения из ряда Фибоаччи
                {
                    pos = i;//Переменной "pos" присваиваем значение переменной "i" чтобы знать на каком шаге мы нашли число которое искали
                    ok = true;//Логической переменной "ok" присваиваем значение "true", так как условие выполнилось.
                    break;//Досрочный выход из цикла.
                }
            }
            if (ok)//Проверяем если переменная "ok" содержит значение "true", то выполняем следующее действие.
            {
                Console.WriteLine("Число N присутствует в ряду Фибоначчи на месте " + pos.ToString());//Вывоод сообщения о том, что число найдено.
            }
            else//Вслучае если переменная "ok" содержит значение "false", то выполняем следующее действие.
            {
                Console.WriteLine("В ряду Фибоначчи число N не присутствует.");//Вывоод сообщения о том, что число не найдено.
            }
            Console.ReadLine();
        }
    }
Тоже давно делал, но в консольке!