Big Fibonacci algoritma sorusu

Jang Geum'un Danji Yemeği · 19 Temmuz 2020

Merhaba arkadaşlar,
Soru şöyle, kaynak: koduesi.com. Sorunun adı Big Fibonacci.

Kod:

Fibonacci sequence is the sequence of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

It is defined as follows: F(0) = 0.
F(1) = 1.
F(n) = F(n-1) + F(n-2) n >1.

Compute the number M(n) = F(n) mod 2^m where (0 <= n <= 2 147 483 647) and (0 <= m < 20).

Input.
The number T of test cases is given in the first line.
Each test case is specified by the numbers n and m, separated by space.

Output.
The number M(n). The result for each test case should be printed in a separate line.

Sample #1.
Input.
2.
11 7.
11 6.
Output.
89.
25.

Ben de uygun bir şekilde algoritmayı oluşturup kodu yazdım. O da çok acemice olabilir, kusura bakmayın.

C:

#include<stdio.h>

long int modal(long int n, long int d) {
return ( n & (d - 1) );
}
long int kuvvetal(unsigned int a,unsigned int b){
unsigned int n,m;
for(n=1;n<=b;n++) m=a*m;
return m;
}
long int fibonacihesapla(unsigned int a){
if(a==1) return 1;
else if(a==2) return 1;
else if(a==0) return 0;
else return fibonacihesapla(a-1)+fibonacihesapla(a-2);
}

int main(){
unsigned int d, k, n, l;
scanf("%u",&n);
for(l=1;l<=n;l++) {
scanf("%u %u",&k,&d);
printf("%ld",modal(fibonacihesapla(k),kuvvetal(2,d)));
}
return 12345;
}

Verdiği örnekleri tutuyor ama cevabı göndettiğimde yanlış kabul ediyor. Yani bir yerde hata yapmışım. Bir türlü bulamayınca sizden yardım isteyeyim dedim. Teşekkürler.
@bitwise

Vavien. · 20 Temmuz 2020

Önce tavsiyeler vereyim. Main'de return 12345 yerine 0 yap. Gerçekten ihtiyacın yoksa unsigned değişken kullanma.

Sanırım istenen bu. Yine kendine göre düzenlersin.

Kod:

#include<stdio.h>
#define MAX 20
#define TWO 2

long mod(long num1, long num2) {
    return ( num1 & (num2 - 1) );
}

long power(long num1, long num2){
    
    long temp = num1;
    
    for (long i = 1; i < num2; ++i){
        num1 *= temp;
    }
    
    return num1;
}

long fib(long num){
    
    long temp0 = 0;
    long temp1 = 1;
    long temp2 = 1;
    
    switch (num){
    case 0:
        return temp0;
    case 1:
        return temp1;
    }
    
    for (long i = 0; i < num - 1; ++i){
        temp2 = temp0 + temp1;
        temp0 = temp1;
        temp1 = temp2;
    }
    
    return temp2;
}

int main(){
    
    int num;
    scanf("%d", &num);
    
    long arr[MAX];
    long arr2[MAX];
    
    for (int i = 0; i < num; ++i){
        scanf("%li %li", &arr[i], &arr2[i]);
    }
    
    for (int i = 0; i < num; ++i){
        printf("%li\n", mod(fib(arr[i]), power(TWO, arr2[i])));
    }

    return 0;
}

Jang Geum'un Danji Yemeği · 20 Temmuz 2020

Vavien. dedi:

Önce tavsiyeler vereyim. Main'de return 12345 yerine 0 yap. Gerçekten ihtiyacın yoksa unsigned değişken kullanma.

Sanırım istenen bu. Yine kendine göre düzenlersin.

Kod:

#include<stdio.h>
#define MAX 20
#define TWO 2

long mod(long num1, long num2) {
    return ( num1 & (num2 - 1) );
}

long power(long num1, long num2){
  
    long temp = num1;
  
    for (long i = 1; i < num2; ++i){
        num1 *= temp;
    }
  
    return num1;
}

long fib(long num){
  
    long temp0 = 0;
    long temp1 = 1;
    long temp2 = 1;
  
    switch (num){
    case 0:
        return temp0;
    case 1:
        return temp1;
    }
  
    for (long i = 0; i < num - 1; ++i){
        temp2 = temp0 + temp1;
        temp0 = temp1;
        temp1 = temp2;
    }
  
    return temp2;
}

int main(){
  
    int num;
    scanf("%d", &num);
  
    long arr[MAX];
    long arr2[MAX];
  
    for (int i = 0; i < num; ++i){
        scanf("%li %li", &arr[i], &arr2[i]);
    }
  
    for (int i = 0; i < num; ++i){
        printf("%li\n", mod(fib(arr[i]), power(TWO, arr2[i])));
    }

    return 0;
}

Hocam zaman limitine takıldı

Bir türlü çözemedim gitti. İçime oturdu.
Neden unsigned değişken kullanmamalıyız?

Vavien. · 20 Temmuz 2020

Mantık operatörleri ile kıyaslarken hata olabiliyor, yanlış değer üretebiliyor. Düzgün IDE'ler uyarır zaten.

Recursive olmamasına rağmen zaman limitine takılması ilginç geldi. Daha güzel Fibonacci fonksiyonları vardır.

Bu arada çok değer giriyorsa fonksiyon çağırmak yerine print eden for'un içine fonlsiyonlar entegre edilebilir. Fonksiyon çağırmanın bir maliyeti var.

En çok kaçıncı Fibonacci sayısını isteyebiliyor? 2 milyara kadar gitmesi gerekiyor mu gerçekten?

Jang Geum'un Danji Yemeği · 20 Temmuz 2020

2 milyarı denetliyorlardır herhalde. Ellerinde örnekler var ve denetiyorlar teker teker.
Denetlemese bile kendimi geliştirmek için çözdüğüm bir soru

Nasıl olduğunu bilsem iyi olur.

Vavien. · 20 Temmuz 2020

Şu şekilde daha hızlı olur normalde ama birkaç denemeden sonra 500 binde sorun çıkarmazken 550 binde sorun çıkartıyor bilgisayarım. 2 MB'cık bir şey. Neden bu kadar laf ediyor anlamıyorum.
Malloc ile daha az verdiğini yazmayı unutmuşum.

Kod:

#include<stdio.h>
#define MAX 20
#define TWO 2

long mod(long num1, long num2) {
    return ( num1 & (num2 - 1) );
}

long power(long num1, long num2){
   
    long temp = num1;
   
    for (long i = 1; i < num2; ++i){
        num1 *= temp;
    }
   
    return num1;
}

long fib(long num){
   
    long arr[500000];
   
    arr[1] = 1;
    arr[2] = 1;
   
    switch (num){
    case 0:
        return 0;
    case 1:
        return 1;
    }
   
    for (long i = 3; i <= num; ++i){
        arr[i] = arr[i - 1] + arr[i - 2];
    }
   
    return arr[num];
}

int main(){
   
    int num;
    scanf("%d", &num);
   
    long arr[MAX];
    long arr2[MAX];
   
    for (int i = 0; i < num; ++i){
        scanf("%li %li", &arr[i], &arr2[i]);
    }
   
    for (int i = 0; i < num; ++i){
        printf("%li\n", mod(fib(arr[i]), power(TWO, arr2[i])));
    }

    return 0;
}

Jang Geum'un Danji Yemeği · 20 Temmuz 2020

Düzgün IDE kullanmıyorum herhalde, uyarmıyor beni Dev C

İyi geceler, özel durumu aramaktan kafam yandı...

Vavien. · 20 Temmuz 2020

Fonksiyonları atıp böyle yaptım. Daha hızlısı çıkmaz benden.

Kod:

#include <stdio.h>
#define MAX 20
#define TWO 2

int main(){
  
    int num;
    scanf("%d", &num);
  
    long arr[MAX];
    long arr2[MAX];
    long arr3[500000];
    arr3[1] = 1;
    arr3[2] = 1;
  
    for (int i = 1; i <= num; ++i){
        scanf("%li %li", &arr[i], &arr2[i]);
    }
  
    for (int i = 1; i <= num; ++i){

        for (long j = 3; j <= arr[i]; ++j){
            arr3[j] = arr3[j - 1] + arr3[j - 2];
        }
        
        long fib = arr3[arr[i]];
        long power = TWO;
        
        for (long j = 1; j < arr2[i]; ++j){
            power *= TWO;
        }

        printf("%li\n", (fib % power));
    }

    return 0;
}

bitwise · 20 Temmuz 2020

Normal fibo serisi : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
m=2 oldugunda (mod 4 e gore) : 0 , 1 , 1 , 2 , 3 , 1 , 0 , 1 , 1 , 2

Dikkat edersen modlar da fibonacci serisi seklinde ilerliyor. O halde fibonacci hesabi yapip sonra genel toplami modlamak yerine her faktor icin modulo hesabi yapip toplamak daha iyi. Cunku m degeri 20 yi gecemez, bu da 32 bit Integer MAX degerden buyul fibonacci faktoru olamayacagi anlamina gelir. Zaten n degerini hayvan gibi tutmuslar, bu da bir isaret. Adam sana normal fibonacci hesaplama diyor. Time complexity'i sorunu olmayacaktir diye tahmin ediyorum, memoization ekledim. Biraz daha matematik kastirarak daha hizlandirilabilir gibi geliyor ama gecenin 2:30 unda bu kadar basti kafam : )

Kotlin implementasyonu:

Kod:

fun main() {
    println(calc(11, 7)) // 89
    println(calc(11, 7)) // 89
    println(calc(11, 6)) // 25
    println(calc(2147483637, 19)) // 370114
}

fun calc(n: Int, m: Int): Int {
    val modulo = 2.0.pow(m.toDouble())
    var v2 = 1 % modulo.toInt()
    var v3 = 1 % modulo.toInt()
    var tmp = -1
    if (n == 0) return 0
    if (n == 1) return v2
    if (n == 2) return v3
    for (i in 3 until n + 1) {
        tmp = (v2 + v3) % modulo.toInt()
        v2 = v3
        v3 = tmp
    }
    return tmp
}

Biraz dusundum uzerine, fibonacci serisi hesaplamana bile gerek yok. sadece 3 variable ile cozersin, ustte bahsettigim matematiksel prensip sebebiyle.

Big Fibonacci algoritma sorusu

Ayrıntılı düzenleme

Jang Geum'un Danji Yemeği

Megapat

Vavien.

Zettapat

Jang Geum'un Danji Yemeği

Megapat

Vavien.

Zettapat

Jang Geum'un Danji Yemeği

Megapat

Vavien.

Zettapat

Jang Geum'un Danji Yemeği

Megapat

Vavien.

Zettapat

bitwise

Megapat

Benzer konular

Yeni konular

Yeni mesajlar

Gizliliğinize önem veriyoruz