0

このサイトで叩かれないことを願っています。私は初心者のプログラマーで、この概念に非常に苦労しています。私はフィボナッチ数列のメモ化を任されています。私は降下を把握していると思いますが、もちろん実装ガイドラインは次のとおりであり、私を混乱させています。

typedef struct Memo
{
// dynamically allocated HugeInteger array to store our Fibonacci numbers
struct HugeInteger *F;

// the current length (i.e., capacity) of this array
int length;
} Memo;

typedef struct HugeInteger
{
// a dynamically allocated array to hold the digits of a huge integer
int *digits;

// the length of the array (i.e., number of digits in the huge integer)
int length;
} HugeInteger;

すでにご覧のとおり、フィボナッチ数は単純な「int」ではなく、int 配列に格納された数値になるため、たとえば int - 134528 は int someNumber[6] = {1,3, のような配列になります。 4,5,2,8}

私はメモを次のように作成しました：

Memo *createMemo(void)
{
/*
Description: Create and initialize a Memo struct:
1. Dynamically allocate space for a new Memo struct.

2. Within the Memo struct, dynamically allocate an array of INIT_MEMO_SIZE number of
HugeInteger structs. INIT_MEMO_SIZE is defined in Fibonacci.h.

Note: This is an array of actual structs, not pointers to structs. So, you cannot set     the
individual elements of this array to NULL, and you cannot free() them.

3. Once the array is created, initialize memo→length appropriately.

4. Make two calls to HugeInit() to initialize F[0] and F[1] (your two Fibonacci base
cases) within the Memo struct.

5. For all remaining F[i], initialize the digits field to NULL and the length field to 0     to
indicate that F[i] has not yet been memoized.

Panic: If any calls to malloc() fail within this function, call panic() (defined in
HugeInteger.c) with the following string argument: “ERROR: out of memory in
createMemo()\n”.

Returns: A pointer to the new Memo struct.
*/
int i;

//Dynamically allocate new Memo
Memo *newMemo = malloc(sizeof(Memo));

        //Check if malloc failed
        if(newMemo == NULL)
            panic("ERROR: out of memory in createMemo()\n");

//Malloc a newMemo->F struct
newMemo->F = malloc(sizeof(HugeInteger *) * INIT_MEMO_SIZE);

        //Check if malloc failed
        if(newMemo->F == NULL)
            panic("ERROR: out of memory in createMemo()\n");

//Initialize the length of the Memo
newMemo->length = INIT_MEMO_SIZE;

//Make two calls to HugeInit to initialize F[0] and F[1] base cases
HugeInit(&newMemo->F[0], 0);
HugeInit(&newMemo->F[1], 1);

//Initialize the rest of F[i] to NULL & length to 0 so I now it's not memoized
for(i=2; i<INIT_MEMO_SIZE; i++)
    {
    newMemo->F[i].digits = NULL;
    newMemo->F[i].length = 0;
    }

//Return the newly created Memo
return newMemo;
}

新しいメモを作成した後、フィボナッチ関数に入ります。これが私の脳が失敗する場所です。私はフィボナッチ関数を次のように実装しました: struct HugeInteger *fib(int n, Memo *memo)

{
/*
Description:
Implement a recursive solution that checks whether F(n) has already been memoized and,     if so,
returns F(n) without making any recursive calls. 

1. If n exceeds the bounds of the array in memo, call expandMemo(). For more information
on what parameters to pass to expandMemo(), refer to its function description above.

3. In order to compute and memoize F(n), you must call the HugeAdd() function that is
defined in HugeInteger.c. The function requires F(n - 1) and F(n - 2) to be memoized
already. HugeAdd() will memoize F(n) if you call it correctly (i.e., it will store the     result
in memo).

Returns: The address of the struct within memo that holds F(n). If memo is NULL or n is     less than
0, return NULL without performing any recursive calls and without calling expandMemo().
*/
int i;

//Handle for negative numbers
if(n < 0 || memo == NULL)
    return NULL;

//Handle for index out of bounds
if(n > memo->length)
    expandMemo(memo, n);

//Check Memory if F[n] already exists and return it
if(memo->F[n].digits != NULL)
    return &memo->F[n];

//return the base cases;
if(n < 2)
    return &memo->F[n];
else
{
    //My thought process was to make two recursive calls and then use the provided
 HugeAdd function to add the information together. HOWEVER the HugeAdd function is a 
void function so it does it's thing and returns nothing. basically it takes the two
arrays and adds them index by index like you would on paper. 
The first argument of Huge add is the first HugeInteger to be added, then the second 
argument is the second HugeInteger to be added, and the third argument is the
HugeInteger where you want the result. second problem I see is that temp1 is never
being malloc'd or initialized so as the fibonacci series grows temp1 will need to be
malloc'd accordingly and then it will need to be filled accordingly. I am lost 
completely as to how to implement this. 

    HugeInteger *temp1 = fib(n-1, memo);
    HugeInteger *temp2 = fib(n-2, memo);

    HugeAdd(&temp1, &temp2, &memo->F[n]);
}

return &memo->F[n];

}

フィボナッチ数をそれぞれの配列スロットに取得し、それらを HugeAdd 関数にプッシュする方法について、私は完全に迷っています。私が概説した機能は変更できません。また、補助機能を作成することしかできません。

私は単に洞察が欲しいだけで、他のみんなと同じようにプログラミング地獄の深さを一人で歩かなければならないことを理解しています.

4

1 に答える 1

0

コメントで指摘したように、HugeIntegerfirst のスタブ実装を使用してプログラムをデバッグするようにしてください。フィボナッチ ルーチンのロジックが機能していることを確認したら、真のHugeInteger実装を統合してみることができます。まず、簡単なスタブを次に示します。

typedef struct HugeInteger {
    unsigned long long digits;
    int length;
} HugeInteger;

void HugeInit (HugeInteger *h, unsigned long long val) {
    h->digits = val;
    h->length = 1;
}

void HugeAdd (const HugeInteger *a, const HugeInteger *b, HugeInteger *c) {
    assert(a->length);
    assert(b->length);
    assert(!c->length);
    c->digits = a->digits + b->digits;
    c->length = 1;
}

void HugePrint (const HugeInteger *a) {
    assert(a->length);
    printf("%llu\n", a->digits);
}

もう1つのポインター。あなたのルーチンでは、配列を適切createMemo()に割り当てていません:F

//Malloc a newMemo->F struct
newMemo->F = malloc(sizeof(HugeInteger *) * INIT_MEMO_SIZE);

のFメンバーはMemoであるHugeInteger *ため、代わりに割り当てsizeof(HugeInteger) * INIT_MEMO_SIZEます。

于 2013-06-12T01:53:38.587 に答える