除算を用いずに配列bを構築する[N]
2448 ワード
配列a[N]が与えられ、配列b[N]が構築され、b[i]=a[0]*a[1]*...*a[N-1]/a[i].構築プロセス:
除算は使用できません.
O(1)空間複雑度とO(n)時間複雑度が要求される.
遍歴カウンタとa[N]b[N]を除いて、新しい変数(スタック一時変数、対空間、グローバル静的変数などを含む)は使用できません.
プログラムで実装し、簡単に説明してください.
少し前に一度やってみましたが、手書きは間違っていて臨界問題はよく考えられませんでした...うっとうしい
デバッグを使用しないでエラーを検出しました..今度はアルゴリズムの正しさを証明することを学ばなければならない.
実はいくつかの方法があります...
除算は使用できません.
O(1)空間複雑度とO(n)時間複雑度が要求される.
遍歴カウンタとa[N]b[N]を除いて、新しい変数(スタック一時変数、対空間、グローバル静的変数などを含む)は使用できません.
プログラムで実装し、簡単に説明してください.
少し前に一度やってみましたが、手書きは間違っていて臨界問題はよく考えられませんでした...うっとうしい
デバッグを使用しないでエラーを検出しました..今度はアルゴリズムの正しさを証明することを学ばなければならない.
1 void func3(int a[], int b[], int n)
2 {
3 b[n-1] = 1;
4
5 for (int i=n-1; i>0; i--)
6 {
7 b[i-1]= b[i]*a[i];
8 }
9 b[n-1]=a[0];
10 for (i=1; i<n-1; i++)
11 {
12 b[i] *= b[n-1];
13 b[n-1] = b[n-1]*a[i];
14 }
15
16 }
実はいくつかの方法があります...