C++で階段の数と各階段の段数をカウントするプログラム

本記事では、配列Aに含まれる情報から、登った階段の数と、それぞれの階段の段数を求めるC++プログラムを紹介します。

問題の概要

n個の要素を持つ配列Aがあるとします。Amalは多層ビルの中で階段を上っており、階段を上るたびに1から数え始めます。例えば、3段と4段の2つの階段を上った場合、「1, 2, 3, 1, 2, 3, 4」のように数字を発します。

配列Aには、Amalが発した階段番号が記録されています。この配列をもとに、彼が何回階段を上ったかをカウントし、さらに各階段の段数を出力する必要があります。

例えば、入力が A = [1, 2, 3, 1, 2, 3, 4, 5] の場合、出力は「2」と「[3, 5]」となります。これは、2つの階段を上り、それぞれが3段と5段であることを意味します。

解法のアプローチ

この問題は以下の手順で解くことができます。

• 配列Aの要素を先頭から順に走査し、値が1になっている箇所をカウントします。これは新しい階段を上り始めたタイミングを示すためです。
• カウントした数が、登った階段の総数になります。
• 次に、値が1である要素の直前の要素を出力します。これは直前の階段の最後の段数（＝その階段の総段数）に相当します。
• 最後に、配列の末尾の要素を出力します。これは最後の階段の段数です。

p = 0
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
    if A[i] is same as 1, then:
        (increase p by 1)
print p
for initialize i := 1, when i < n, update (increase i by 1), do:
    if A[i] is same as 1, then:
        print A[i - 1]
print A[n - 1]

C++による実装例

理解を深めるために、実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> A) {
    int i, p = 0;
    int n = A.size();
    for (i = 0; i < n; i++) {
        if (A[i] == 1)
            p++;
    }
    cout << p << endl;
    for (i = 1; i < n; i++) {
        if (A[i] == 1)
            cout << A[i - 1] << ", ";
    }
    cout << A[n - 1];
}
int main() {
    vector<int> A = { 1, 2, 3, 1, 2, 3, 4, 5 };
    solve(A);
}

入力

{ 1, 2, 3, 1, 2, 3, 4, 5 }

出力

2
3, 5

コードの解説

このプログラムでは、まず最初のループで配列内の「1」の出現回数を数えています。「1」は階段を上り始める合図なので、その回数が階段の総数pになります。

次のループでは、「1」が出現した位置の一つ前の要素を出力しています。例えば、インデックス3の値が1の場合、インデックス2の値「3」は最初の階段の段数を表します。

最後に配列の末尾の要素「5」を出力することで、最後の階段の段数も表示されます。これにより、階段の数「2」と各階段の段数「3, 5」が正しく得られます。