1、选秀节目打分，分为专家评委和大众评委，score[] 数组里面存储每个评委打的分数，judge_type[] 里存储与 score[] 数组对应的评委类别，judge_type[i] == 1，表示专家评委，judge_type[i] == 2，表示大众评委，n表示评委总数。打分规则如下：专家评委和大众评委的分数先分别取一个平均分（平均分取整），然后，总分 = 专家评委平均分 * 0.6 + 大众评委 * 0.4，总分取整。如果没有大众评委，则 总分 = 专家评委平均分，总分取整。函数最终返回选手得分。
函数接口 int cal_score(int score[], int judge_type[], int n)
本题比较简单，按照C语言的顺序结构进行就可以。对专家评委和大众评委分开计算，分别引入两个变量，一个用来统计评委的人数count，另一个用来统计评委的分数总和sum。这样就可以分别求出各自的平均分。可以通过count来判断是否有专家评委。
1
int cal_score(int score[], int judge_type[], int n)
2
{
3
int expertCount = 0;
4 int commonCount = 0;
5 int expertTotal = 0;
6 int commonTotal = 0;
7 for(int i = 0;i<n;++i)
8
{
9 if(judge_type[i] == 1)
10 {
11 expertCount++;
12 expertTotal+=score[i];
13
}
14 if(judge_type[i] == 0)
15 {
16 commonCount++;
17 commonTotal+=score[i];
18 }
19 }
20 if(commonCount==0)
21 {
22 return (expertTotal/expertCount);
23 }
24 else
25 {
26 return (int)(expertTotal/expertCount*0.6+commonTotal/commonCount*0.4);
27 }
28 return 0;
29
}
2、给定一个数组input[] ，如果数组长度n为奇数，则将数组中最大的元素放到 output[] 数组最中间的位置，如果数组长度n为偶数，则将数组中最大的元素放到 output[] 数组中间两个位置偏右的那个位置上，然后再按从大到小的顺序，依次在第一个位置的两边，按照一左一右的顺序，依次存放剩下的数。
例如：
input[] = {3, 6, 1, 9, 7} output[] = {3, 7, 9, 6, 1};
input[] = {3, 6, 1, 9, 7, 8} output[] = {1, 6, 8, 9, 7, 3}
函数接口 void sort(int input[[], int n, int output[])
根据题目要求，我们可以先对input进行由大到小排序，我采用的是最简单的选择排序算法。然后先将最大值存入到output的中间位置。（因为C/C++语言的数组小标是从0开始的，当n为偶数的时候，n/2即是中间偏右的位置）。然后对input从小标[1,n)开始遍历，先插入左边后插入右边。中间位置mid = n/2;引入一个变量step，来表示每次向左右移动的距离，每次移动后step自增1。向左移动后为mid-step，向右位置为mid+step。每次遍历，循环变量i增大2。
void sort(int input[], int n, int output[])
{
if(n<2)
return;
int mid = n/2;
int pos =1,step=1;
//进行简单的选择排序，由大到小
for(int i=0;i<n;++i)
{
for(int j=i+1;j<n;++j)
{
if(input[j]>input[i])
{
int t = input[i];
input[i] = input[j];
input[j] = t;
}
}
}
//先确定最大元素的位置
output[mid] = input[0];
while(pos<n)
{
output[mid-step] = input[pos++];
if(pos>=n)
break;
output[mid+step] = input[pos++];
step++;
}
}
3、操作系统任务调度问题。操作系统任务分为系统任务和用户任务两种。其中，系统任务的优先级 < 50，用户任务的优先级 >= 50且 <= 255。优先级大于255的为非法任务，应予以剔除。现有一任务队列task[]，长度为n，task中的元素值表示任务的优先级，数值越小，优先级越高。函数scheduler实现如下功能，将task[] 中的任务按照系统任务、用户任务依次存放到system_task[] 数组和 user_task[] 数组中（数组中元素的值是任务在task[] 数组中的下标），并且优先级高的任务排在前面，优先级相同的任务按照入队顺序排列（即先入队的任务排在前面），数组元素为-1表示结束。
例如：task[] = {0, 30, 155, 1, 80, 300, 170, 40, 99} system_task[] = {0, 3, 1, 7, -1} user_task[] = {4, 8, 2, 6, -1}
函数接口 void scheduler(int task[], int n, int system_task[], int user_task[])
因为system_task和user_task中存储的是task优先级由高到低的下标。我们要保持task前后保持不变，方便我们找出任务的具体下标。我采用用空间换取时间的思想，引入一个数组temps，将task的元素拷贝过去，然后对temp进行由小到大的排序（数值越小优先级越大），我采用的是快速排序。然后遍历temps，在task中查询temps[i]在task中对应位置pos，然后根据系统任务和用户任务的条件进行判断，将pos插入到相应的队列中。在函数结束时，要释放temps。
void scheduler(int task[], int n, int system_task[], int user_task[])
{
int sysIndex =0,userIndex = 0;
int pos;
//引入一个临时的数组来存储有序的task
int *temps = new int[n];
memcpy(temps,task,n*sizeof(int));
qsort(temps,n);
//寻找任务在task中的下标
for(int j=0;j<n;++j)
{
for(int k=0;k<n;++k)
if(task[k] == temps[j])
{
pos = k;
break;
}
if(temps[j] <50)
system_task[sysIndex++] = pos;
else
if(temps[j]>=50 && temps[j] <=255)
user_task[userIndex++] = pos;
}
system_task[sysIndex] = -1;
user_task[userIndex] = -1;
delete temps;
}
void qsort(int datas[],int n)
{
if(n<2)
return;
//随机选择一个中轴
swap(datas,0,rand()%n);
int pos = 0;
for(int i=1;i<n;++i)
if(datas[i] < datas[0])
swap(datas,++pos,i);
//最终确定中轴的位置
swap(datas,0,pos);
//比中轴小的部分
qsort(datas,pos-1);
//比中轴大的部分
qsort(datas+pos+1,n-pos-1);
}
void swap(int datas[],int n,int m)
{
int temp = datas[n];
datas[n] = datas[m];
datas[m] = temp;
}
posted on 2011-10-05 20:08
Anker 阅读(349)
评论(0) 编辑 收藏 引用 所属分类:
笔试与面试题