c - 木の計算と印刷

Question

次のようなツリーを構築する必要があります。

したがって、ユーザーから 2 つの数字を受け取りaますb。a行数をb定義し、ルート ノードの開始値を定義します。a=5 とb=3 の場合、次のようになります。

私は基本的にそれをコンソールに出力するだけです。どうやって始めればいいのか、本当に迷っています。誰かが私を正しい方向に少し押してくれませんか?

Answer 1

これはパスカルの三角形で、行 n、列 k の値は b * (n choose k) です。ここで、n と k は両方ともゼロ インデックスであり、(n choose k) = n! / (k! * (nk)!)

これを理解したら、問題の解決策は、関数を作成int choose(int n, int k)し、コンソールに四角形を配置することになります。

レイアウトは最も難しい部分ですが、アプローチは次のとおりです。

1. まず、数値を印刷する幅を選択する必要があります。たとえば、W としましょう。おそらく W = 3 が適切でしょう。
2. 次に、各行の先頭に印刷するスペースの数を把握する必要があります。各行は印刷部分に W + 1 幅を追加するため、後続の各行の前に (W + 1) / 2 少ないスペースが必要であり、行 (a - 1) で 0 スペースで終了します。つまり、(a - n - 1) * (W + 1) / 2 スペース前に行 n に配置されます。
3. 第三に、関数を書く必要がありますint choose(int n, int k)
4. 最後に、行を繰り返し処理する必要があります。最初に手順 2 で決定されたスペースの数を出力し、次に手順 3 の関数を使用して計算された数値を出力しますprintf("%-*d ", W, b * choose(n, k));。

Answer 2

1 つの方法は、ツリーを下方向に「成長」させることです。行数が与えられると、ツリー内の要素数を把握し、適切なサイズの配列を割り当てることができます。

次に、1 から番号が付けられた行を想定して、一番上から開始します。down_left(x) = x + row(x)ここxで、 は配列インデックスでrow(x)あり、 は行番号がx属しています。down_right(x) = down_left(x) + 1.

上から始めて、down_left と down_right に進みます。次に、作成した次の行の各要素に対して、「親」番号の累積効果を得るために下の行に追加することを除いて、同じことを行います。

たとえば、ユーザーが 3 行と 3 のルート値を要求した場合。

6 つの配列要素が必要になることがわかっています。6 つの要素を割り当ててゼロにします。

3行 1:配列 [0] に置きます。行 n: 前の行の各要素を見て作成し、それを i と呼びます。次に、array[down_left(i)] += iと を行いarray[down_right(i)] += iます。これにより、行 n が作成されます。繰り返す。

とにかく、それは大まかなアイデアです。プレイして、どこに到達するかを確認してください... :)