上位３位までを出力するとき、同点が複数いた場合の処理の方法

Question

<プログラムの目的>
２０人の学生の「学生番号、名前、３科目の点数」がまとめられたファイルを読み込み、３科目の合計点数が高い上位３人を出力する。なお、上位３位までに同点の生徒がいた場合は全員出力する。

１位、２位、３位が複数いた場合は全員出力。１位が一人、２位が一人、３位が二人の場合は、四人出力。

１位が２人、２位が０、３位が２人の場合は、四人出力。

１位が４人の時は、四人出力。

ファイルは以下の形式。
1001 name 49 50 23
1002 name 22 79 43
......

<質問内容>
３科目の合計点数が高い順に出力まではできました。ただ、同点の生徒がいた場合の処理がわからないです。どうすれば同じ点数の学生を全員出力できるのでしょうか。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 256

//まずは構造体。
typedef struct {
  int num;//学生番号
  char name[SIZE];
  int sub1;//科目1
  int sub2;//科目2
  int sub3;//科目3
  int sum;//３科目の合計
} students;

students s[20];

//３科目の合計点数を降順に。
void bubble_sort(int n, students s[]) {
  students tmp;
  int i, j;

  for (i=0; i<n; i++) {
    for (j=n-1; j>i; j--) {
      if (s[j].sum > s[j-1].sum) {
        tmp = s[j];
        s[j] = s[j-1];
        s[j-1] = tmp;
      }
    }
  }
}

//最後の出力
void print_students(students s) {
  printf("%d,%s,%d\n", s.num, s.name, s.sum);
}

int main(int argc, char *argv[]) {
  FILE *fp;
  char line[SIZE], name[SIZE];
  int i, sub1, sub2, sub3, num, sum[20];


  //エラー処理
  if ((fp = fopen(argv[1], "r"))== NULL) {
    printf("Can't open the file.\n");
    return 1;
  }
  //配列が空じゃない時に回り続ける。
  i = 0;
  for (; fgets(line, SIZE, fp) != NULL ;) {
    sscanf(line, "%d %s %d %d %d", &num, name, &sub1, &sub2, &sub3);

    //値をバンバン代入していく。まずはsum.
    s[i].sum = sub1 + sub2 + sub3;
    // printf("%d\n", s[i].sum);

    //次に、name.
    strcpy(s[i].name, name);

    //次に、num.
    s[i].num = num;
    i++;

    }

  bubble_sort(20, s);

//これだと
　int z = 3;
  for (i=0; i<z; i++) {
    print_students(s[i]);
    if (s[i].sum == s[i+1].sum) {
      z++;
    }
  }

  fclose(fp);```ここに言語を入力
コード

return 0;
}

Comments

[jimbe]

>どうすれば同じ点数の学生を全員出力できるのでしょうか
まさしくそれがこの課題のキモですから、丸投げで聞くのはダメなのではないでしょうか。

実は案外簡単なので、閃きさえあればコードはすぐ書けます。頑張ってみてください。

[hagito]

返信ありがとうございます。

焦りに焦ってしまい、丸投げという形で質問してしまいました。次から気をつけます。

Answer 1

3番目に出力した人(3位とは限らない)と同じ点数の人を全員出力すればいいのではないでしょうか？

コ－ドを書いてみてください。

Answer 2

ヒントだけ。

1. 配列sの最初の3要素s[0], s[1], s[2]は必ず出力する。
2. 配列sの4つめの要素s[3]からs[19]までは、条件が成り立つ間は出力する。

1は、「上位3人を出力」という要件から導かれる。
2は、「上位3位までに同点の生徒がいた場合は全員出力する」という要件から導かれる。

よって、「s[3]から繰り返し処理して、どのような条件が成り立つ間は出力するか」という問題を考えればいい。

これは、「任意のnに対して、上位n人を出力。ただし、上位n位までに同点の生徒がいた場合は全員を出力」という問題よりも限定されているため、簡単に書くことができる。

Comments

[jimbe]

最後の一文は変数が n だけだと何か変ではないでしょうか…。

Answer 3

ソートできたなら、順位をつけましょう

Comments

[episteme]

回答になっていない。低評価。

[y_waiwai]

順位をつけたなら、
１位のものを全部出力、
出力人数が３人以上ならおしまい
２位のものを全部出力
出力人数が３人以上ならおしまい
３位のものを全部出力

というコードをかけばいいだけですねー

[episteme]

うん、だから質問者は「(同点なら同順位って条件の下で)どうやって順位をつけるんでしょうか?」と訊いてるに等しいのでは?

[y_waiwai]

私は、順位の付け方を聞いてるようには見えませんが。
んで、他の回答も順位の付け方の回答じゃないし、どうしましょうかこれ

[episteme]

- とにかく上位三名を出力
- それ以降、三人目と同点である限り出力
ならば、順位つけなくてもいい。
てか、順位がつけられるくらいなら解ける問題、
それに対して「順位をつけましょう」では回答にならんだろ、と僕は考えます。

[y_waiwai]

ひとの考えかたはいろいろですねえ

[episteme]

↑そのとおり。とはいえ「ひとそれぞれ」で済ませたらミもフタもない。

Answer 4

BA 選択後はもう御覧になっていらっしゃらないでしょうか。

#include <stdio.h>

#define N 10
#define M 3

int main(int argc, char *argv[]) {
  int sordeddatas[][N]={
      { 100, 99, 98, 98, 97 }, //一位1人,二位1人,三位2人
      { 100, 100, 98, 98, 97 }, //一位2人,二位0,三位2人
      { 100, 100, 100, 100, 99 }, //一位4人
      { 100, 99, 98, 97 }, //各位1人
      { 100, 99, 99, 98 }, //一位1人,二位2人
      { 100, 99, 99, 99, 98 }, //一位1人,二位3人
      { 0 }, //全員0点
      { -1 } //EOD
  };

  for(int i=0; sordeddatas[i][0]>=0; i++) {
    int *scores = sordeddatas[i];

    //上位M位内点の出力
    for(int j=0; j<N && (j<M || scores[j]==scores[j-1]); j++) { //[j-1] は [M-1] でも OK
      printf("%d ", scores[j]);
    }
    printf("\n");

  }
  return 0;
}

100 99 98 98 
100 100 98 98 
100 100 100 100 
100 99 98 
100 99 99 
100 99 99 99 
0 0 0 0 0 0 0 0 0 0 

Answer 5

ソートしない方法．

２０人分のデータから　合計点数を横軸，人数を縦軸にしたヒストグラム　を作る．

↓

（点数の高い側から）binを見ていく．

値が1以上のbin(点数)について，その点数の生徒を全て表示する．
binの値と同数の表示を行うことになるはずである．
表示した人数の総数は処理全体を通してカウントしておく．

あるbinに関する上記処理が終わった際に，カウント値が3以上なら処理終了とする．

Comments

[fana]

前提条件として「合計点数」の最大値が 300点だ とか既知とできるなら，
頭空っぽにして要素数300の配列とかでヒストグラムを表現してもよいだろう．

あるいは「人数が２０人」という側が既知なので，合計点数の種類は最大でも２０種類しかないから，要素数２０の配列的なので表現しても良いだろう．

[fana]

> その点数の生徒を全て表示する

と言う処理が若干馬鹿馬鹿しい気もするが，
たかだか２０人のデータだし，この処理自体を最高でも３回しかやらないハズだから，「処理効率がどうの」とか言うほどでもなかろう．

20要素の生徒データを最大で４回なめるだけだ（そのうち１回はヒストグラム生成）．

Answer 6

表示した人数が3人より多い、かつ前の人の得点と違う得点の場合にbreakすればいいです。

Answer 7

3位の人の点数を求め（これは出来ているはず）、
その点数以上の人を全員出力（人数数える必要なし）すれば目的が果たせるかと思います。

Comments

[jimbe]

一位が4人の時はその4人だけを表示ですので、この方法では仕様を満たせないと思います。

[otn]

あー、言葉が不正確でした。誤指摘ありがとうございます。
誤：3位の人の点数
正：ソートした状態で、配列の上から3つめの要素の点数

Answer 8

※ 計算量を意識せずにやるならなんとかできそうなので、計算量は度外視しています。
(そこ突っ込まれると対応できない……)

---

まず、泥臭い感じで考えてみましょう。

つまり、「プログラミングとかは置いといて、現実世界でならどうするか」です。

そもそもプログラミングっていうのは『こう書けばいい』ではなく、「プログラミングは現実世界のシミュレーションである」です。

なので、まずは現実世界で考えてみてください。

方法は今思いつくものだと大きく分けて2つありますね。

一つは、「ソートしてから決める」です。

orig = { 10, 9, 5, 7, 2, 7, 4, 7 }

だと、

ranked = { 2, 4, 5, 7, 7, 7, 9, 10 }

となりますね。(ただし点数だけに着目した場合とする)

で、この中から一位を考えるとどうなるでしょうか。

普通に末尾の10 ですね。

二位は? その次の 9 ですね。

三位は? 7 ですが、なんか3つありますね。

ってことは、

一位: 10, 二位: 9, 三位: 7, (7,7,7)

となっていますね。

では、どのように「複数あるか」を判別するでしょうか。

そう、「両隣を見て、同じ数字かどうか」を見ればいいだけです。

末尾 = 最上位

ということは決定しているので、後ろから見ていきましょうか。

後ろから見て、i = (N-1) の場合、つまり arr[n-1] のような場合は、
その前のデータ、(N-2)番目、つまり arr[n-2] を参照して、同じ値かをチェックする。

上記で設定した、ranked 配列だと、10 と 9 を比較して同じかどうかを見る。

10 == 9 ? 同じですか? 違いますね。

なので、「これ以上同列は無し」として、一位はこれだけ。

ranked[n-1] には 10 ではなく -1 とかみたいな「もうここは除外する」的な意味のものを入れておく。

次に第二位ですが、これは ranked[n-2] を見る。
そして、その一個前のranked[n-3] を比較する。

9 == 7 ? 同じですか? 違いますね。なので第一位と同じように「これ以上ない」とします。
そして ranked[n-2] を 9 ではなく -1 みたいなデータに書き換える。

さらに第三位も決める。

ranked[n-3]ですが、7 ですね。
その一個前のデータ ranked[n-4] を見てみましょう。

7 == 7 ? ありゃ、同じですね。次はこのranked[n-4]を軸にして考えます。

ranked[n-4] と ranked[n-5] を比較する。

7 == 7 ? ありゃ、これも同列。

ranked[n-5]を軸にして その一個前の ranked[n-6] を比較。

7 == 5 ? これは全く違いますね。

ってことでここで終わりですね。

そうすると、上記のように求められる。

構造体の場合は、この数列を構造体の列と読みかえてください。

後はもうちょっと詰めればわかるはずです。

---

もう一つの方法は『ソートせずに行う』です。

質問者さんは

orig = { 10, 9, 5, 7, 2, 7, 4, 7 }

とあったら、現実世界ではどのようにやりますか?

ここでもまた2種類思いつきますね。

一つは「1~3位の数字を決定してからその数字を拾っていく方法」。
もう一つは「順位を決定していきながら拾っていく方法」。

1~3位の数字を決定してからその数字を拾っていく方法を考えてみましょう。

まず、orig = { 10, 9, 5, 7, 2, 7, 4, 7 }を対象にやってみましょう。

※ ただ、値は後から取り出すため、コピーを取っておいた方がよさそうです。

orig ではなく、コピーした orig_tmp にします。

最初は先端、数列だと初項に相当する部分を見る。

orig_tmp[0] = 10 なので、10 を暫定第一位としますか。

一位: 10
場所: 0番目

とホワイトボードかなんかに書いておく。

でもまだデータはあるので、次のorig_tmp[1]を見る。

そして、暫定一位と比較してみる。

暫定一位 < orig_tmp[i] となれば 更新する。

10 < 9 は満たしますか? 満たしませんね。

なのでスルー。

さらに orig_tmp[2] も比較。

10 < 5 は満たしますか? 満たしませんね。スルー。

……と最後までやると、

一位: 10
場所:0番目

となっています。

なので、0番目が第一位。

でも次回以降は同じ数列を対象に第二、第三位を決めるので、orig_tmp[0]を除外した方がよさそうです。

なので orig_tmp[0] を -1 とかみたいな、「ここにはデータはねーぞ」という意味のデータに書き換えておく。

ノートとかであれば、 "---" とかみたいに。

そうすると、

orig_tmp = { ---, 9, 5, 7, 2, 7, 4, 7 }

みたいになる。

で、第二位を決める。

orig_tmp[0] を見ようとしますが、すでに取り除かれているため、スルー。

なので orig_tmp[1] から見る。

すると orig_tmp[1] = 9 なので暫定二位は 9 。

[決定]
一位: 10

[調査中]
二位: 9
場所: 1番目

…とこれも同じようにやると、やはり第二位は9 になる。

なので9がある orig_tmp[1] を　「ここにはねーぞ」という意味のものに書き換える。

orig_tmp = { ---, ---, 5, 7, 2, 7, 4, 7 }

第三位も決めましょうか。

orig_tmp[0], orig_tmp[1] は「何もない」となっているのでスルー。

つまり orig_tmp[2]から開始。

orig_tmp[2] = 5 なので、

[決定]
一位: 10
二位: 9

[調査中]
三位: 5
場所: 2番目

となる。

で、次の orig_tmp[3] を見ると、orig_tmp[3] = 7 ですね。

暫定三位 = 5
orig_tmp[3] = 7

5 < 7 なので、暫定三位が更新されます。

[決定]
一位: 10
二位: 9

[調査中]
三位: 7   ← 5 から 7 へ書き換え
場所: 4番目 ← 3 から 4 へ書き換え

orig_tmp[5] もやりますが、これは変化なし。( 7 < 2 は満たさないので )

orig_tmp[6] もやります。

でも 7 < 7 は満たしますか? 満たしませんね。7 は含んではいけないので。

……とやると、

[決定]
一位: 10
二位: 9

[調査中]
三位: 7
場所: 4番目

となりますね。

なので、4番目を伏字にしようか…と思いましたが、三位まででいいので以降は計算しないので、スルー。

さあ、1~3位が決まりました。

[決定]
一位: 10
二位: 9
三位: 7

後は、「同列があればそれも列挙する」的な処理です。

後はそのまま origから10 に該当するもの、9 に該当するもの、7に該当するものをすべて列挙すればいいだけです。

上記は 順位の決定 -> 該当するデータの抽出 という二段階になっています。

もう一つの方法である、「順位を決定していきながら拾っていく方法」はこの二段階の処理を同時に行う感じです。

Comments

[BeatStar]

あ、解決してたっぽい……

[jimbe]

この課題は、順位を意識しながら考えると面倒になるのではないでしょうか。
どちらかというと「現実のシミュレーション」の課題というよりは、「現実のパターン化」の課題かと思います。

Answer 9

int z = 3;
for (i=0; i<z; i++) {
print_students(s[i]);
for (; s[i].sum == s[i+1].sum ;) {
i++;
print_students(s[i]);
}
if (i > 3) break;
}

Comments

[kazuma-s]

本当に解決ですか？
全員同じ点数の場合どうなりますか？
例えば全員 0点の場合。

[jimbe]

Daregada さんや kazuma-s さんの回答の「部分」があるのは確かですが、惜しいというかちょっと違うというか…
アハ体験としてはコードを直接提示させて頂くのもアリですが、課題でしょうから憚られますし。