6

約 20 分前に入門 C コースの試験を終えたところです。試験の最初の質問は、私をやや不意を突かれたもので、2 つの大きな数の違いを見つけるというものでした。

目標は、2 つの構造体 (N1 と N2) を値で取得し、その違いを参照渡しの構造体 (N3) に格納することでした。N3 はすべて「0」で開始されたと想定できます。MAX サイズは何でもかまいませんので、数値が 100 桁を超える場合でもソリューションは機能する必要があります。

ベースコードは次のとおりです（元は少し異なる場合があります。これはメモリからのものです）

#include <stdio.h>
#include <stdlib.h>
/* MAX can be any length, 10, 50, 100, etc */
#define MAX 10

struct bignum
{
    char digit[MAX];
    char decimaldigit[MAX/2];
};
typedef struct bignum bigNum;
void difference(bigNum, bigNum, bigNum *);

/*
    Original values in N1 and N2

    N1.digit = { '0', '0', '0', '5', '4', '8', '2', '0', '9', '0'};
    N1.decimaldigit { '0', '0', '0', '4', '9' };

    N2.digit = { '0', '0', '0', '4', '8', '1', '3', '1', '4', '5'};
    N2.decimaldigit { '8', '0', '1', '2', '0' };
*/

/*
    Result would be:
    N3.digit = { '0', '0', '0', '0', '6', '6', '8', '9', '4', '4'}
    N3.decimaldigit { '1', '9', '9', '2', '9' }
*/

問題は、この問題の解決策を見つけることではありませんが、完全な回答に対して約 20 行しか提供されていません。私の解決方法は、整数に変換した後に数字を 1 つずつ減算し、結果が負の場合は適切なキャリーを作成することでした。これは、提供されたものよりもかなり多くのスペースを必要としました。

この質問に与えられたわずかなマークとスペースに基づいて、私が見ていないかなり些細な解決策があると信じるに至りました。それは何ですか？私はコースを終了しましたが、この質問はまだ私を悩ませています!

完全なソリューションは必要ありません。関数の内部の仕組みだけですdifference。

念のため、ビット単位の演算子は使用しないでください。

4

3 に答える 3

10

ほとんどのコンピューター サイエンス クラスの BigNumber 問題は、記述どおりに正確に「手で」算術を行う必要があるように設計されています。各文字を整数に変換し、必要に応じて減算し、借用します。

あなたが説明したように、あなたの計画攻撃はほんの数行である必要があります。疑似コードでは、次のようになります。

for each character (right to left):
    difference = N1.digit[i] - N2.digit[i];
    if (difference < 0)
        N1.digit[i - 1]--;
        difference += 10;
    N3.digit[i] = difference;

(さらに、同じロジックを 10 進数にも適用するのは少し手間がかかります。)

あなたは正しい考えを持っていたように思えますが、おそらく実装を考えすぎましたか?

于 2009-08-22T20:27:28.283 に答える
6

の場合、これは機能するはずですN1 >= N2。これは、配列が のように配置されていることも前提としていますdn...d2d1d0.e0e1...em。

char digchr(int); // Converts a single-digit integer into a character.

void difference(bigNum N1, bigNum N2, bigNum *N3) {
    int carry = 0;

    for (int i = MAX / 2 - 1; i >= 0; i--) {
        int diff = N1.decimalDigits[i] - N2.decimalDigits[i] - carry;
        if (diff < 0) { 
            diff += 10;
            carry = 1;
        } else {
            carry = 0;
        }

        N3->decimalDigits[i] = digchr(diff);
    }

    for (int i = 0; i < MAX; i++) {
        int diff = N1.digits[i] - N2.digits[i] - carry;
        if (diff < 0) {
           diff += 10;
           carry = 1;
        } else {
            carry = 0;
        }

        N3->digits[i] = digchr(diff);
    }
}
于 2009-08-22T20:28:40.247 に答える
3

親愛なる教授、引き算は足し算で定義されるべきです。単項「-」演算子をオーバーロードし、bignum 加算ルーチンを別の場所で定義しました。私は9の補数を使用して、テーブルベースの回答ルックアップで加算を簡素化/高速化します（厄介なキャリーは必要ありません！）（10個しかないのに合計を計算するのはなぜですか？）。bigNum 減算ルーチン (仕様に合わせて) は次のとおりです。

void bigDifference(bigNum N1, bigNum N2, bigNum *N3) {
    bigSum(N1, -N2, N3);
}
于 2009-08-24T20:47:14.820 に答える