Array algorithms: max, count, search, average · 配列アルゴリズム：最大値、カウント、検索、平均
Four classic array jobs
- Most array work is one of four scans: find the maximum, count matches, search for a value, or take an average.
- Each one is a single
forloop over the array, with a variable that remembers something. - Once you know these four, most array problems are a small change to one of them.
4つの古典的な配列タスク
- ほとんどの配列操作は4つのスキャンのいずれかです：最大値の探索、一致のカウント、値の検索、または平均値の取得。
- 各タスクは、配列全体を一度だけ巡る単一の
forループであり、何かを記憶する変数を使います。 - これら4つを知れば、ほとんどの配列問題はそれらのいずれかの小さな変形になります。
Finding the maximum
- Start by assuming the first item is the biggest:
int best = a[0];. - Then look at the rest. If an item is bigger than
best, it becomes the newbest. - This works for negative numbers too, because you start from a real item, not
0.
最大値を見つける
- まず、最初の要素が最大だと仮定します：
int best = a[0];。 - それから残りの要素を見ます。もしある要素が
bestより大きいなら、それが新しいbestになります。 - 負の数にも適用されます。なぜなら、
0ではなく実際の要素から始めるからです。
Counting with a condition
- A counter starts at
0and adds1each time an item passes a test. - For example, count even numbers by testing
a[i] % 2 == 0inside the loop. - The counter's final value is your answer.
条件付きでのカウント
- カウンタは
0から始まり、要素が条件を満たすたびに1を加えます。 - 例えば、ループ内で
a[i] % 2 == 0をテストすることで偶数の数をカウントします。 - カウンタの最終値があなたの答えです。
Linear search
- To search, walk the array and compare each item to the target.
- Return the index as soon as you find a match. If the loop ends with no match, return
-1. -1is a common "not found" signal because it is never a valid index.
線形探索
- 検索するには、配列をトレースして各要素をターゲットと比較します。
- 一致が見つかったら即座にインデックスを返します。ループが終了しても一致がない場合は、
-1を返します。 -1は「見つかりません」の一般的なシグナルとして使われます。なぜなら、有効なインデックスではないからです。
Average without integer-division bugs
- Add all the items into an
inttotal, then divide byn. - Dividing two
ints drops the fraction, so cast:(double)total / n. - Return a
doubleso the caller gets the exact average.
整数除算バグのない平均値
- 全要素を
int累加器に足し、それをnで割ります。 - 2つの
intを割ると小数点以下が切り捨てられるため、キャストが必要です：(double)total / n。 doubleを返すことで、呼び出し側に正確な平均値を手渡せます。
Common mistakes
- Start a max or min from the first element, then compare the rest.
- Do not read past the end of the array.
よくあるミス
- 最大値または最小値の計算は、最初の要素から始め、残りを比較する。
- 配列の先 Beyond 読まないでください。
Now you try
- Pass the array and its length
n, and pick the right "remember" variable for each job. - Do not write a
main— the checker provides one.
あなたも試してみよう
- 配列とその長さ
nを渡し、各タスクに適切な「記憶」変数を選んでください。 mainを書かないでください；チェックツールが用意します。
Scanning an array · 配列のスキャン
One pass keeps a running result (max, sum, count) across the array. · 1回のパスで、配列全体にわたる累積結果（最大値、合計、カウント）を維持します。
Complete int max(const int a[], int n) so it returns the largest item (assume n >= 1). Start from a[0] so negatives work. Do not write a main. · int max(const int a[], int n)を完成させて、最大値（n >= 1と仮定）を返すようにする。a[0]から始め、負の数が正しく処理されるようにする。mainは書かない。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
Complete int count_even(const int a[], int n) so it returns how many items are even. Use % 2. Do not write a main. · int count_even(const int a[], int n)を完成させて、偶数要素の数を返すようにする。% 2を使用する。mainは書かない。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
Complete int index_of(const int a[], int n, int target) so it returns the index of the first target, or -1 if it is not there. Do not write a main. · int index_of(const int a[], int n, int target)を完成させて、最初のtargetのインデックスを返すか、存在しない場合は-1を返すようにする。mainは書かない。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
Complete double average(const int a[], int n) so it returns the average of the items (assume n >= 1). Cast to avoid integer division. Do not write a main. · double average(const int a[], int n)を完成させて、要素の平均値を返すようにする（n >= 1と仮定）。整数除算を防ぐために型変換を行う。mainは書かない。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。