Wieder (vielleicht) Erstaunliches vom Fibonacci

1 Lösung

#156

Anfänger - C von hollst - 19.04.2017 um 15:47 Uhr

Gegeben sei eine Folge von N Strings der Längen 1, 2, 3 ... N. Jedes Char eines Strings beinhaltet lediglich entweder eine '0' oder eine '1',
jedoch dürfen zwei benachbarte Chars nicht beide eine '1' beinhalten.

Man zeige für N bis 25, dass die Anzahl möglicher (unterschiedlicher) Strings einer Längenklasse der Fibonacci-Reihe ab der 2 folgen
(2, 3, 5, 8 ...).

Also:

Länge = 1, zwei Möglichkeiten ("0", "1")
Länge = 2, drei Möglichkeiten ("00", "01", "10")
Länge = 3, fünf Möglichkeiten ("000", "001", "010", "100", "101")
...

Wieviele unterschiedliche Strings der oben genannten Art gibt es mit einer Stringlänge von 999?

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von devnull (8870 Punkte) - 27.04.2017 um 17:53 Uhr

Konsolenausgabe:

Länge =  2 :       3
Länge =  3 :       5
Länge =  4 :       8
Länge =  5 :      13
Länge =  6 :      21
Länge =  7 :      34
Länge =  8 :      55
Länge =  9 :      89
Länge = 10 :     144
Länge = 11 :     233
Länge = 12 :     377
Länge = 13 :     610
Länge = 14 :     987
Länge = 15 :    1597
Länge = 16 :    2584
Länge = 17 :    4181
Länge = 18 :    6765
Länge = 19 :   10946
Länge = 20 :   17711
Länge = 21 :   28657
Länge = 22 :   46368
Länge = 23 :   75025
Länge = 24 :  121393
Länge = 25 :  196418
Große Länge = 999:
7033036771142281582183525487718354977018126983635873
2742604905087154537118196933579742249494562611733487
7504492417659910881863632654502236471060120533741212
73867339111198139373125598767690091902245245323403501

C-Code

/**************************************************
 * nfib.c  Anzahl Fibonacci-Zahlen für 0/1-Strings
 **************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <values.h>
# include <gmp.h>
 
#define MAXLEN 25
#define BIGLEN 999 

/* aus C-140 */
void calc_fibonacci(int number)
{
    mpz_t fn, fnn, fsum;
    int n;
  
    mpz_init(fn);
    mpz_init(fnn);
    mpz_init(fsum);
  
    mpz_set_ui(fn, 0L);
    mpz_set_ui(fnn, 1L);
    for (n=2; n<=number; n++) {
        mpz_add(fsum, fn, fnn);
        mpz_set (fn, fnn);
        mpz_set (fnn, fsum);
    }
    gmp_printf("%Zu\n", fnn);
}

/* Test auf Bitmuster innerhalb Zahl */
int contains(unsigned number, int len, unsigned bitpattern) {
  unsigned mask = bitpattern;
  unsigned msb = ~(~0u>>1);
  int plen = INTBITS;
  int shift;

  while ((mask&msb) == 0) {
    msb >>= 1;
    --plen;
  }
  shift = len - plen;
  while (shift-- >= 0) {
    if ((number&mask) == mask)
        return 1;
    mask <<= 1;
  }
  return 0;
}

/* main */
int main()
{
    int nfib[MAXLEN];
    int i, imax, n;

    nfib[0] = 2;
    for (n=2; n<=MAXLEN; n++) {
        imax = 2<<(n-1);
        nfib[n-1] = 0;
        for (i=0; i<imax; i++) {
            if (contains(i,n,3))
                continue;
            ++nfib[n-1];
        }
        printf("Länge =%3d : %7d\n", n, nfib[n-1]);
    }
    printf("Große Länge = %3d:\n", BIGLEN);
    calc_fibonacci(BIGLEN+2);
    return 0;
}