VPF::[Java] Числа Фибоначчи - Форум программистов

Merhaba

Дата 18.5.2011, 18:07 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 93
Регистрация: 23.4.2011

Репутация: нет
Всего: нет

Добрый Вечер!!!
Помогите Пожалуйста написать код, который будет очень быстро вычислять числа фибоначчи с номерами от 3 до 50000 .
Первый элемент последовательности - 1;
Второй элемент последовательности - 1;
Я пытался написать программу через рекурентную формулу, но вычисляет очень долго:

Код


import java.math.BigInteger;

public class FibonacciNumber {


 static BigInteger getByLoopWithBigInteger(int n) {
 BigInteger a = new BigInteger("1");
 BigInteger b = new BigInteger("1");

for (int i = 0; i < n; i++) {
BigInteger saveA = a;
a = b;
 b = saveA.add(a);
}

return a;
}

public static void main(String[] args) {
System.out.println("Число Фибоначчи: "
        +FibonacciNumber.getByLoopWithBigInteger(50000));
}
}

помогите Пожалуйста переделать код, чтобы он считал в "системе счисления по основанию k^l <= 10^6"

mes

Дата 19.5.2011, 00:41 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: нет
Всего: 250

Цитата(Merhaba @ 18.5.2011, 17:07

)

через рекурентную формулу, но вычисляет очень долго:

вот на C++

Код



size_t fib (size_t n)
{
     if (n==0 || n==1) return 1;

     size_t a = 1;
     size_t b = 1;          
       
     for (;;) {
     
        a += b; 
        if ( --n == 1 ) return a;
     
        b += a;
        if ( --n == 1 ) return b;     

     } 
}

--------------------

http://opendots.net

Merhaba

Дата 19.5.2011, 06:19 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 93
Регистрация: 23.4.2011

Репутация: нет
Всего: нет

mes,
а как можно написать код, чтобы вычисляло очень быстро?

Silent

Дата 19.5.2011, 16:32 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 252
Регистрация: 3.10.2006

Репутация: 6
Всего: 9

Держи, но я не проверял на правильность, хотя должно все работать:

Код


//Внимание! данный код содержит ошибку!
import java.util.*;

public class Fibb
{
   public static void main(String[] args)
   {
     Scanner in = new Scanner(System.in);
        int n = in.nextInt(), 
            k = in.nextInt(), 
            l = in.nextInt(),
            pow = 1,
            a = 1, b = 1;
    
        for (int i = 1; i <= l; i++) pow *= k;
        for (int i = 3; i <= n; i++)
        {
            a = b;
            b = (a + b) % pow;
        }
        System.out.println(b);
    }
}

Но данный код оставляет желать лучшего - 50000 сложений-остатков. Есть алгоритм ПОБЫСТРЕЕ! Писать код, Merhaba, я за тебя не буду (если ты, конечно, лапки кверху не поднимешь), но дам пару подсказок:
1) числа фиббоначчи лучше вычислять так: http://algolist.manual.ru/maths/count_fast/fibonacci.php, через матричные операции.
2) а возведение в степень (для пункта 1) лучше делать так: http://algolist.manual.ru/maths/count_fast/fast_exp.php

Сколько тебе дать времени на размышления-написания? Или мне сразу шустрый код привести? smile

Это сообщение отредактировал(а) Silent - 20.5.2011, 22:03

Merhaba

Дата 19.5.2011, 21:06 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 93
Регистрация: 23.4.2011

Репутация: нет
Всего: нет

Silent,
Приведите Пожалуйста сразу шустрый код)
А то я серъёзно лапки кверху подниму

Silent

Дата 20.5.2011, 22:16 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 252
Регистрация: 3.10.2006

Репутация: 6
Всего: 9

Что ж Вы так быстро сдались smile

даже не было попыток подумать
поскольку с Java я не на короткой ноге, то приведу код на C# (VS2010) - отличия крайне незначительны
Версия v0, приводилась мной в предыдущем сообщении, и содержала ошибку (теперь все правильно):

Код


using System;
using System.IO;

public class Fibb
{
    public static int Main(String[] args)
    {
        string[] tokens = ((new StreamReader("input.txt")).ReadLine()).Split(' ');
        int n = int.Parse(tokens[0]),
            k = int.Parse(tokens[1]),
            l = int.Parse(tokens[2]);
        int pow = 1,
            a = 1,
            b = 1;

        for (int i = 1; i <= l; i++) pow *= k;
        for (int i = 3; i <= n; i++)
        {
            int tmp = (a + b) % pow;
            a = b;
            b = tmp;
        }
        StreamWriter fout = new StreamWriter("output.txt");
        fout.WriteLine(b);
        fout.Close();
        return 0;
    }
}

Данный код является линейным и требует O(N) операций. Для 50000 можно использовать и его - на моей машине вычисления выполнялись за 32мс.

Вторая версия v1, использующая матричную алгебру реккурентных формул, и быстрое возведение в степень:

Код


using System;
using System.IO;

public class matrix
{
    int a, b, c, d;    //{{a,b},{c,d}}
    public matrix(int a, int b, int c, int d)
    {
        this.a = a;
        this.b = b;
        this.c = c;
        this.d = d;
    }

    //умножение матрицы на матрицу
    public void mulMod(matrix x, int m)
    {
        int a1 = a * x.a + b * x.c;
        int b1 = a * x.b + b * x.d;
        int c1 = c * x.a + d * x.c;
        int d1 = c * x.b + d * x.d;
        a = a1 % m;
        b = b1 % m;
        c = c1 % m;
        d = d1 % m;
    }

    //умножение матрицы на вектор
    public int[] mulMod(int x, int y, int m)
    {
        int[] res = new int[2];
        res[0] = (a * x + b * y) % m;
        res[1] = (c * x + d * y) % m;
        return res;
    }

    //быстрое возведение матрицу в степень, x >= 2
    public void powMod(int x, int m)
    {
        matrix bb = new matrix(this.a, this.b, this.c, this.d);
        while (x != 0)
        {
            if (x % 2 == 1) this.mulMod(bb, m);
            bb.mulMod(bb, m);
            x >>= 1;
        }
    }
}

public class Fib
{
    private static int pow(int n, int m)
    {
        int bb = n;
        int res = 1;
        while (n != 0)
        {
            if (n % 2 == 1) res *= bb;
            bb *= bb;
            n >>= 1;
        }
        return res;
    }

    private static int Main()
    {
        string[] tokens = new StreamReader("input.txt").ReadLine().Split(' ');
        int n = int.Parse(tokens[0]),
        k = int.Parse(tokens[1]),
        l = int.Parse(tokens[2]),
        m = pow(k, l);
        StreamWriter fout = new StreamWriter("output.txt");
        if (n <= 2) fout.WriteLine(1);
        else
        {
            matrix a = new matrix(0, 1, 1, 1);
            a.powMod(n, m);
            int[] ans = a.mulMod(0, 1, m);
            fout.WriteLine(ans[0]);
        }
        fout.Close();
        return 0;
    }
}

Для 50000 я также не заметил никакой задержки выполнения (те же 32мс), но для бОльших значений разница будет, как говорится, на лицо. Особенно это будет заметно, если необходимо посчитать не по модулю. Количество операций - O(logN).

(Если не разберешься с переводом C#->Java, придется-таки мне скачивать и ставить что-нить для java-кода)

Merhaba

Дата 21.5.2011, 09:25 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 93
Регистрация: 23.4.2011

Репутация: нет
Всего: нет

Silent,
Если Вас не затруднит, помогите Пожалуйста перевести вот этот код на Java.

Код


int n = int.Parse(tokens[0]),
            k = int.Parse(tokens[1]),
            l = int.Parse(tokens[2]);
        int pow = 1,
            a = 1,
            b = 1;

        for (int i = 1; i <= l; i++) pow *= k;
        for (int i = 3; i <= n; i++)
        {
            int tmp = (a + b) % pow;
            a = b;
            b = tmp;
        }

Merhaba

Дата 21.5.2011, 22:57 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 93
Регистрация: 23.4.2011

Репутация: нет
Всего: нет

Silent,
Объясните Пожалуйста первый способ и почему там int tmp = (a + b) % pow;
за что отвечает l ?

Это сообщение отредактировал(а) Merhaba - 21.5.2011, 22:58

Silent

Дата 23.5.2011, 22:32 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 252
Регистрация: 3.10.2006

Репутация: 6
Всего: 9

Код


int n = int.Parse(tokens[0]),
            k = int.Parse(tokens[1]),
            l = int.Parse(tokens[2]);

я не знаю как это будет на Java, но суть кода - програма получает на вход консоли строку, которую разбирает на три токена (вход - три параметра, n, k, l), которые преобразуются из строки в число. Гугль мне подсказывает, что данный код перепишется так:

Код


int n = Integer.parseInt(token[0]),
     k = Integer.parseInt(token[1]),
     l = Integer.parseInt(token[2]);

остальное вроде точно так же что в C#, что в Java

Просите пояснение про первый способ... не знаю как объяснить, я не математик, но остаток от суммы можно считать вот таким образом, посмотрите, пожалуйста, теорию чисел, в сторону модулярной арифметики.

Merhaba

Дата 24.5.2011, 07:31 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 93
Регистрация: 23.4.2011

Репутация: нет
Всего: нет

Silent,

Если Вас не затруднит, объясните Пожалуйста вот эту строчку: int tmp = (a + b) % pow;
почему там a+b ?

m1st

Дата 10.4.2012, 17:46 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 73
Регистрация: 1.11.2006

Репутация: нет
Всего: нет

Решение этого задания есть тут: Задачи на числа. Решение. Покритикуйте. (часть №1)

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »