0

大学の課題として以下の問題が出ました。

ゲーム人数をNとし、それぞれに1からNまでの番号があるとする。K番から順にM番目の人はゲームから抜け、その度にその次の番号から数えてM番目の人が抜けるのを繰り返す。最後に残った人の番号を計算するプログラムを作れ。入力の一行目はNとゲーム回数、続けて各行に各ゲームのKとMを入力する。出力は最後に残った人の番号をそれぞれ一行ずつ出力すること。

このプログラムをvectorを使って作ってみましたが、入力する数字によっては「double free or corruption (out)」と表示されてしまいます。swapなどを使ってもエラーは直らず、どこが間違っているのかご指摘いただきたいです。

#include<iostream>
#include<vector>
using namespace std;
inline void Check(int kazu, int k, int m, vector<int> a){
    int i;
    for(int j = 1; j < kazu; j++){
    i = k + m;//消す位置
    if(i > a.size())i %= a.size();
    a.erase(a.begin() + i - 1);
    k = i;//次に始める場所
    }
    cout << a[0] << endl;
}
int main()
{
    int kazu, n;// ゲーム人数, ゲーム回数
    cin >> kazu >> n;
    vector<vector<int>> lol(n, vector<int>(2));
    for(int j = 0; j < n; j++){
        cin >> lol[j][0] >> lol[j][1];// = k, m
        lol[j][1] -= 1;} //mを間隔にする
    vector<int> a;
    for(int j = 1; j <= kazu; j++){
        a.push_back(j);
    }
    int k, m;
    for(int j = 0; j < n; j++){
        k = lol[j][0], m = lol[j][1];
        Check(kazu, k, m, a);
    }
    return 0;
}

上手くいく入力例

5 2
1 3
2 2

出力例

4
4

上手くいかない入力例

6 1
1 3

また、以下は助教からヒントとしてもらった解答例に少し変更を加えたものです。この中のvis[]while{}の中で何故そのように書くのか、どういう仕組みなのかが理解できません。これも教えていただきたいです。よろしくお願いします。

解答例

#include<stdio.h>
int main(){
    int kazu, n, k, m;
    scanf("%d %d", &kazu, &n);
    while(n != 0){
    scanf("%d %d", &k, &m);
    int vis[100] = { 0 };
    int count = 0;
    int rev = kazu;
    while (rev != 1) {
        count++;
        if (count == m) {
            vis[k] = 1;
            rev--;
            count = 0;
        }
        do {
            k = k % kazu + 1;
        } while (vis[k] == 1);
    }
    printf("%d\n", k);
    n -= 1;
    }
    return 0;
}
0

1 件の回答 1

4
a.erase(a.begin() + i - 1);

i = 0 となった際には、先頭の一つ手前、無効な要素を削除しようとします。

std::vector<T>::eraseを使われていますが、これは名前の通り指定されたインデックスの要素を削除し前に詰める機能です。当たり前ですが、前に詰めるため、以降の処理は要素のインデックスがずれますし、サイズも1つ減ります。
対して解答例は固定長配列を 0 / 1 で指定しているだけですのでインデックスやサイズが変化することはありません。

変数名がぐちゃぐちゃで処理を読む気はありませんが、両者の違いを考慮して処理を変更する必要があります。


蛇足ですが、変数名を解答例と揃えたりしないのでしょうか? 解答例で n, num となっている部分が質問者さんのコードでは kazu, n となっていて、 n の意味が異なりますが、質問者さんご自身は混乱しませんか?

1
  • なるほど、回答ありがとうございます。変数名のほうはそこまで気が回りませんでした。次から読みやすいコードにするよう気をつけます。 Commented 2020年4月8日 15:24

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。