65451


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

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

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

[code]

    #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, ｍ
            lol[j][1] -= 1;}　//ｍを間隔にする
        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;
    }
    
[/code]

上手くいく入力例

[code]

    5 2
    1 3
    2 2
    
[/code]

出力例

[code]

    4
    4
    
[/code]

上手くいかない入力例

[code]

    6 1
    1 3
    
[/code]

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

解答例

[code]

    #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;
    }
    
[/code]


CC BY-SA 4.0
2020-04-07T16:18:15.727
65448
2020-04-08T03:36:18.793
2020-04-08T03:36:18.793
3060
39446
question
c++
c++ vector メモリの二重開放？


>
[code]

>     a.erase(a.begin() + i - 1);
>  
[/code]

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

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

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

* * *

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


CC BY-SA 4.0
2020-04-07T22:07:37.813
65451
2020-04-07T22:07:37.813
4236
65448
answer