第24次比赛第1题之测试程序 -- 业余空间-- 编程爱好者博客

第1题之测试程序:
/*
  Name:  选美大奖赛
  Copyright: c 语言趣味程序
  Author:  梁见斌
  Date: 13-04-06 16:08
  Description:
在选美大奖赛的半决赛现场，有一批选手参加比赛，比赛的规则是最后的得分越高，名次越低。
当半决赛结束时，要在现场按照选手的出场顺序宣布最后得分和最后名次，获得相同分数的选手具有相同的名次，
名次连续编号，不要考虑同名次的选手人数。例如：
选手序号：1，2，3，4，5，6，7
选手得分：5，3，4，7，3，5，6
则输出名次为：3，1，2，5，1，3，4
请编程帮助大奖赛组委会完成半决赛的评分排名工作。

函数接口：void ScorePlace(int place[], const int score[], int num);
输入：存储选手名次的数组place[]，存储选手得分的数组score[]，选手人数num。
输出：存储选手名次的数组place[]。

示例1：
输入：score[] = {2,8,5,1,10,5,9,9};
输出：place[] = {2,4,3,1, 6,3,5,5};
示例2：
输入：score[] = {7,7,6,6,7};
输出：place[] = {2,2,1,1,2};
*/

#include <iostream>
#include <time.h>
using namespace std;

void ScorePlace(int place[], const int score[], int num);
void ScorePlace_c(int place[], const int score[], int num);

int main()
{
      time_t startTime;
    time_t endTime;
      const int NUM = 100000;
      int score[NUM] = {0};
      int place1[NUM] = {0};
      int place2[NUM] = {0};
      int sum = 0;
      int i;

      time(&startTime);
      for (int k=0; k<100; k++)
      {
            int max = rand()%(NUM-10) + 10;
            //cout << "max=" << max << endl;
            for (i=0; i<max; i++)
          {
              score[i] = rand()%101 + 1;
          }

          ScorePlace_c(place1, score, max);//参考程序
          ScorePlace(place2, score, max);//选手程序

          for (i=0; i<max; i++)
          {
              if (place1[i] != place2[i])
                        break;
          }
          if (i == max)
                sum++;
      }
      time(&endTime);

      cout << "sum = " << sum << endl;
      cout << "time = " << difftime(endTime, startTime) << endl;

      getchar();
      return 0;
}

void ScorePlace_c(int place[], const int score[], int num)
{
      int *sameScore = new int[num];
      int numPlace = 1;  //选手的名次

      for (int i=0; i<num; i++)//为每个选手的名次设初值为0，表示还未对其排名
            place[i] = 0;

      for (int i=0; i<num; i++)//遍历数组，每次处理一个名次
      {
            if (place[i] == 0)//如果还未对该元素进行排名
            {
                  int min = score[i]; //取该元素作为当前最小值
                  int same = 0;
                  sameScore[same] = i;//记录分值为min的（即具有相同名次）元素的个数

                  for (int j=i+1; j<num; j++)//对余下元素进行处理
                  {
                        if (place[j] == 0)
                        {
                              if (score[j] < min)//若该元素比min小，取该元素作为当前最小值
                              {
                                    min = score[j];
                                    same = 0;  //重新记录分值为min的（即具有相同名次）元素的个数
                                    sameScore[same] = j;
                              }
                              else if (score[j] == min)//若该元素等于min，则其属于具有相同名次的元素
                              {
                                    sameScore[++same] = j; //分值为min的（即具有相同名次）元素的个数增一
                              }
                        }
                  }
                  for (int k=0; k<=same; k++)//对具有相同名次的元素进行排名
                  {
                        place[sameScore[k]] = numPlace;
                  }

                  numPlace++; //名次增一
                  i = -1; //重新查找下一个尚未排名的元素进行排名处理
            }
      }
      delete []sameScore;
}

博客介绍

正文

第24次比赛第1题之测试程序 2006-04-17 20:50:00

评论