争取时间,把握未来,修炼内功!
【QQ:627686595】【Email:weishi2007@126.com】
posts - 2,  comments - 0,  trackbacks - 0
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来判断是否有专家评委。
 1int 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 阅读(324) 评论(0)  编辑 收藏 引用 所属分类: 笔试与面试题

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


开始认真学习《算法导论》第二版,欢迎大家一起讨论。

<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿

随笔分类

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜