面试准备之常见上机题目搜罗

转自：http://blog.csdn.net/kkkkkxiaofei/article/details/22592255

1.从考试成绩中划出及格线

（1）及格线是10的倍数

（2）保证至少有60%的学生及格

（3）如果有所有的学生都高于60分，则及格线为60分。

算法分析：

    关键信息点为“保证至少有60%的学生及格”，可将分数线的概念转换为人数，即只需统计每个档次的人数，若60以上档次的人数就是全体人员则分数线为60，否则去寻找（由高分到低分）最先达到60%人数的档次。

java实现如下：

[java] view plaincopyprint?在CODE上查看代码片派生到我的代码片
 
  1. public class Exam{  
  2.     public int findPassLine(int[] scores){  
  3.         int num=scores.length;  
  4.         int[] record=new int[num+1];//记录每一个档次的人数  
  5.         for(int i=0;i<num;i++){  
  6.           switch(scores[i]/10){  
  7.             case 10:record[10]++;break;  
  8.             case 9:record[9]++;break;  
  9.             case 8:record[8]++;break;  
  10.             case 7:record[7]++;break;  
  11.             case 6:record[6]++;break;  
  12.             case 5:record[5]++;break;  
  13.             case 4:record[4]++;break;  
  14.             case 3:record[3]++;break;  
  15.             case 2:record[2]++;break;  
  16.             case 1:record[1]++;break;  
  17.             case 0:record[0]++;break;  
  18.           }  
  19.       }  
  20.       int sumh=0;//记录60分以上所有人数  
  21.       int suml=0;//记录60分以下所有人数  
  22.       for(int j=record.length-1;j>=0;j--){  
  23.         if(j>=6)  
  24.          sumh+=record[j];  
  25.       }  
  26.       suml=10-sumh;  
  27.     if(sumh==10){//所有人都在60分以上  
  28.             System.out.println("所有人的分数均高于60，分数线为：");  
  29.             return 60;  
  30.       }  
  31.       else{  
  32.         //有高分档次向下遍历  
  33.           for(int k=record.length-1;k>0;k--){//10~0遍历  
  34.             if(record[k]>=6){  
  35.                     return 10*k;        
  36.             }  
  37.             else  
  38.              record[k-1]+=record[k];//向下累加  
  39.           }  
  40.       }  
  41.       return 0;  
  42.     }  
  43.       
  44.     public static void main(String[] args){  
  45.       int a[]={99,89,79,69,0,0,4,5,80,50};  
  46.       System.out.println(new Exam().findPassLine(a));  
  47.       int b[]={100,100,100,100,100,80,0,0,0,0};  
  48.       System.out.println(new Exam().findPassLine(b));  
  49.       int c[]={100,100,100,100,100,100,0,0,0,0};  
  50.       System.out.println(new Exam().findPassLine(c));  
  51.       int d[]={100,100,100,100,100,100,60,80,70,90};  
  52.       System.out.println(new Exam().findPassLine(d));  
  53.     }  
  54. }  

输出：

50
80
100
所有人的分数均高于60，分数线为：
60

2.亮着电灯的盏数

     一条长廊里依次装有n(1 ≤ n ≤ 65535)盏电灯，从头到尾编号1、2、3、…n-1、n。每盏电灯由一个拉线开关控制。开始，电灯全部关着。
    有n个学生从长廊穿过。第一个学生把号码凡是1的倍数的电灯的开关拉一下；接着第二个学生把号码凡是2的倍数的电灯的开关拉一下；接着第三个学生把号码凡是3的倍数的电灯的开关拉一下；如此继续下去，最后第n个学生把号码凡是n的倍数的电灯的开关拉一下。n个学生按此规定走完后，长廊里电灯有几盏亮着。
注：电灯数和学生数一致。 

    算法分析：无任何算法可言，只需要按照题目描述实现一边，不知道有啥捷径

    java实现如下：

[java] view plaincopyprint?在CODE上查看代码片派生到我的代码片
 
  1. //import java.lang.StringBuilder;  
  2. public class Light{  
  3.       
  4.     public int lightNum(int[] lights){  
  5.         //刚开始默认全部打开，1开，0闭  
  6.         int i=1,n=lights.length-1,num=0;  
  7.         while(i<=n){  
  8.             for(int j=1;j<=n;j++){//遍历1--n栈灯(0号元素忽略)  
  9.                 if(j%i==0){  
  10.                     if(lights[j]==1){  
  11.                         //开着的等被关闭  
  12.                         lights[j]=0;  
  13.                         num--;  
  14.                     }  
  15.                     else if(lights[j]==0) {  
  16.                         //关闭的灯被打开  
  17.                         lights[j]=1;  
  18.                         num++;  
  19.                     }  
  20.               }  
  21.             }     
  22.             i++;//第i个人  
  23.         }  
  24.         return num;  
  25.     }  
  26.     //打印亮着的编号  
  27.     public void printLightsNum(int[] lights){  
  28.         StringBuilder sb=new StringBuilder();  
  29.         sb.append("它们分别是:");  
  30.         for(int i=1;i<=lights.length-1;i++){  
  31.             if(lights[i]==1){//开着  
  32.                 sb.append(" ");  
  33.                 sb.append(i);  
  34.             }  
  35.         }  
  36.         System.out.println(sb.toString());  
  37.     }  
  38.       
  39.     public static void main(String[] args){  
  40.         for(int i=10;i<=100;i+=10){  
  41.             System.out.println("初始时"+i+"栈灯灭着!");  
  42.             int[] lights=new int[i+1];  
  43.             Light obj=new Light();  
  44.             System.out.println("触动后还剩下"+obj.lightNum(lights)+"栈灯开着！");  
  45.             obj.printLightsNum(lights);  
  46.             System.out.println("--------------------------------------------------");  
  47.       }  
  48.     }  
  49.   
  50. }  


输出：

初始时10栈灯灭着!
触动后还剩下3栈灯开着！
它们分别是: 1 4 9
--------------------------------------------------
初始时20栈灯灭着!
触动后还剩下4栈灯开着！
它们分别是: 1 4 9 16
--------------------------------------------------
初始时30栈灯灭着!
触动后还剩下5栈灯开着！
它们分别是: 1 4 9 16 25
--------------------------------------------------
初始时40栈灯灭着!
触动后还剩下6栈灯开着！
它们分别是: 1 4 9 16 25 36
--------------------------------------------------
初始时50栈灯灭着!
触动后还剩下7栈灯开着！
它们分别是: 1 4 9 16 25 36 49
--------------------------------------------------
初始时60栈灯灭着!
触动后还剩下7栈灯开着！
它们分别是: 1 4 9 16 25 36 49
--------------------------------------------------
初始时70栈灯灭着!
触动后还剩下8栈灯开着！
它们分别是: 1 4 9 16 25 36 49 64
--------------------------------------------------
初始时80栈灯灭着!
触动后还剩下8栈灯开着！
它们分别是: 1 4 9 16 25 36 49 64
--------------------------------------------------
初始时90栈灯灭着!
触动后还剩下9栈灯开着！
它们分别是: 1 4 9 16 25 36 49 64 81
--------------------------------------------------
初始时100栈灯灭着!
触动后还剩下10栈灯开着！
它们分别是: 1 4 9 16 25 36 49 64 81 100
--------------------------------------------------


 

    从输出中反推原理：最后亮着灯的编号都是可以开方的数，这时为什么呢？

    题中告知所有灯刚开始是关着的，也就说最后想开着，必须触动开关奇数次，即"该灯所对应的编号数，其公约数有奇数个"。那么问题就转化为"什么样的数有奇数个公约数",由于已经知道答案了(完全平方数)，所有只好用反证法。

  证：   若对任意实数C具有奇数个公约数，且C不是完全平方数

             则有C的任意一对公约数m1!=m2，设C有n对公约数，

             则C的公约数总数=n*2+2(可以被自身和1整除)=2*(n+1)为偶数

             此结论与已知"C具有奇数个公约数"矛盾，故C是完全平方数。

    有了上面的结论，即可以直接去找1--n内的完全平方数即可,复杂度就降为O(n)了，我想这就是华为将此题做为中级难度题目的捷径思路了吧。

   

3.验证括号是否匹配

    输入一串字符串，其中有普通的字符与括号组成（包括‘（’、‘）’、‘[’,']'）,要求验证括号是否匹配，如果匹配则输出0、否则输出1.
Smple input：dfa(sdf)df[dfds(dfd)]    Smple outPut:0

    算法分析：利用栈来实现，所有左括号入栈，遇到右括号就进行出栈，看是否匹配。

java实现：

[java] view plaincopyprint?在CODE上查看代码片派生到我的代码片
 
  1. import java.util.Scanner;  
  2. import java.util.Stack;  
  3. public class Match{  
  4.     public static void main(String[] args){  
  5.         Boolean isMatch=true;  
  6.         Stack<Character> stack=new Stack<Character>();  
  7.         Scanner s=new Scanner(System.in);  
  8.         while(true){  
  9.             char ch=s.nextLine().charAt(0);  
  10.             if(ch=='q')  
  11.               break;  
  12.             else{  
  13.                         switch(ch){  
  14.                             case '{':;  
  15.                             case '[':;  
  16.                             case '(':  
  17.                                 stack.push(ch);break;  
  18.                             case '}':  
  19.                                 if(stack.empty())  
  20.                                     isMatch=false;  
  21.                                 else if(stack.pop()!='{')  
  22.                                     isMatch=false;  
  23.                                     break;  
  24.                             case ']':  
  25.                                     if(stack.empty())  
  26.                                     isMatch=false;  
  27.                                 else if(stack.pop()!='[')  
  28.                                     isMatch=false;  
  29.                                     break;  
  30.                             case ')':  
  31.                                 if(stack.empty())  
  32.                                     isMatch=false;  
  33.                                 else if(stack.pop()!=')')  
  34.                                     isMatch=false;  
  35.                                     break;  
  36.                         }  
  37.                 }  
  38.         }  
  39.         if(isMatch)  
  40.             System.out.println("匹配！");  
  41.         else  
  42.             System.out.println("不匹配");  
  43.     }  
  44. }  


C/C++:

[java] view plaincopyprint?在CODE上查看代码片派生到我的代码片
 
  1. void main()    
  2. 13.{//子函数声明     
  3. 14.    void InitStack(SqStack &S);//初始化空栈     
  4. 15.    int StackEmpty(SqStack S);//判空     
  5. 16.    void push(SqStack &S,int e);//进栈     
  6. 17.    void pop(SqStack &S,int &e);//出栈     
  7. 18.    //主函数开始     
  8. 19.    SqStack s;//初始化空栈     
  9. 20.    InitStack(s);    
  10. 21.    char ch[100],*p;int e;    
  11. 22.    p=ch;    
  12. 23.    printf("输一个含义有()[]{}的括号表达式: ");    
  13. 24.    gets(ch);    
  14. 25.    while(*p)    
  15. 26.    {     
  16. 27.        switch (*p)    
  17. 28.        {    
  18. 29.        case '{':    
  19. 30.        case '[':    
  20. 31.        case '(': push(s,*p++);break;//只要是左括号就入栈     
  21. 32.        case '}':    
  22. 33.        case ']':    
  23. 34.        case ')':pop(s,e);    
  24. 35.                 if ((e=='{' && *p=='}') ||(e=='[' && *p==']') || (e=='(' && *p==')'))    
  25. 36.                 p++;    
  26. 37.                 else    
  27. 38.                 {printf("括号不匹配!");exit(OVERFLOW);}    
  28. 39.                 break;    
  29. 40.        default :p++;//其他字符就后移     
  30. 41.        }    
  31. 42.    }    
  32. 43.    if (StackEmpty(s))    
  33. 44.      printf("括号匹配成功");    
  34. 45.    else    
  35. 46.      printf("缺少右括号！");    
  36. 47.    printf(" ");    
  37. 48.}    


 

4.回文数

    判断回文数，是返回1
    算法分析：既然是对称的，那么从个位开始，逆序反向生成一个数，若该数与原数相同，则是回文数。

[java] view plaincopyprint?在CODE上查看代码片派生到我的代码片
 
  1. Scanner s=new Scanner(System.in);  
  2.       int num=s.nextInt();  
  3.       int max=num,min=0;  
  4.       while(max>0){  
  5.         min=min*10+max%10;//反向生成  
  6.         max=max/10;//去除最后一位  
  7.       }  
  8.       if(min==max)  
  9.         System.out.println("Yes");  
  10.       else  
  11.         System.out.println("No");  


附：回文数还有一个性质，即数字位数与存在的回文数有如下关系，

    1位回文数： 9个

    2位回文数： 9个

    3位回文数： 90个

    4位回文数： 90个

    5位回文数： 900个

    6位回文数： 900个

    …

即每增加两位，则存在的回文数为原来的10倍。

5.将整数倒序输出，剔除重复数据

    输入一个整数，如12336544，或1750，然后从最后一位开始倒过来输出，最后如果是0，则不输出，输出的数字是不带重复数字的，所以上面的输出是456321和571。如果是负数，比如输入-175，输出-571。
    算法分析：将每一位存储，存储时剔除重复元素，而后输出。（注意符号）

[java] view plaincopyprint?在CODE上查看代码片派生到我的代码片
 
  1. public static void main(String[] args){   
  2.      Scanner s=new Scanner(System.in);  
  3.           int num=s.nextInt();  
  4.           int[] store=new int[]{99,99,99,99,99,99,99,99,99,99,99,99,99};//初始值不要赋个位数，避免和取余后的数等值  
  5.           int len=0,tmp=num,last;  
  6.           while(true){  
  7.             if(tmp==0)  
  8.                 break;  
  9.             else{  
  10.                         int lastNum= tmp%10;//取余求最后一位  
  11.                         tmp=tmp/10;  
  12.                         int flag=1;//待插入数组中是否含有该数  
  13.                         for(int k=0;k<=len;k++){  
  14.                             if(store[k]==lastNum){  
  15.                                 flag=0;//重复则不插入  
  16.                                 break;  
  17.                             }  
  18.                         }  
  19.                         if(flag!=0){  
  20.                             store[len]=lastNum;//需要插入  
  21.                             len++;  
  22.                         }  
  23.              }  
  24.           }  
  25.           //len指向待插入位置  
  26.           if(num<0)  
  27.                 System.out.print("-");  
  28.           for(int j=0;j<len;j++){  
  29.             if(store[j]!=0)  
  30.             System.out.print(Math.abs(store[j]));  
  31.           }  
  32.     }  


 

 6.大数相减


    输入两行字符串正整数，第一行是被减数，第二行是减数，输出第一行减去第二行的结果。

    备注：1、两个整数都是正整数，被减数大于减数

示例：

输入：1000000000000001

                                         1

输出：1000000000000000

    注意大数用char a[] 存储，用%s接收，一位一位的运算。注意a[0]里的正负号

    算法描述：一位一位减，最高位无需借位。不仅可以大减小，也可以小减大(大减小取负即可)。

java实现：

[java] view plaincopyprint?在CODE上查看代码片派生到我的代码片
 
  1. public int[] subtraction(int[] a,int[] b){  
  2.         int[] c=new int[a.length];  
  3.         //a[0]...a[n]代表高位到低位  
  4.         for(int i=c.length-1;i>=0;i--){  
  5.             //最高位不借位  
  6.             if(i!=0){  
  7.                     if(a[i]<b[i]){  
  8.                         a[i-1]-=1;//向高位借位  
  9.                         a[i]+=10;  
  10.                     }     
  11.             }  
  12.             c[i]=a[i]-b[i];//存储对应位的差值  
  13.         }  
  14.         return c;  
  15.     }  


输出：

    2 7 8 7 1 0 0 2 9 4 0 7 0 8 3 3 8 7 0 6
-   2 5 1 3 7 3 8 8 8 3 1 7 5 2 3 7 3 6 1 2 
----------------------------------------------------
    0 2 7 3 3 6 1 4 1 0 8 9 5 5 9 6 5 0 9 4


    0 8 4 9 2 7 2 5 7 8 4 8 1 3 1 0 6 1 7 9
-   2 0 2 1 6 0 4 9 2 8 8 0 6 3 3 0 2 0 5 8 
----------------------------------------------------
   -1 1 7 2 3 3 2 3 5 0 3 2 5 0 1 9 5 8 7 9


    6 6 5 5 5 1 1 1 5 6 5 5 1 6 2 1 9 7 2 9
-   0 2 8 5 9 7 5 8 9 8 2 8 0 1 8 5 7 3 3 4 
----------------------------------------------------
    6 3 6 9 5 3 5 2 5 8 2 7 1 4 3 6 2 3 9 5


    3 4 7 5 7 1 1 1 9 1 9 2 2 0 0 4 5 2 9 8
-   5 9 5 6 1 5 8 9 8 9 7 1 9 7 1 2 5 0 3 5 
----------------------------------------------------
   -2 4 8 0 4 4 7 7 9 7 7 9 7 7 0 7 9 7 3 7


    5 1 9 0 4 6 1 6 1 6 5 3 1 9 9 3 8 5 9 5
-   4 0 2 2 8 3 3 4 8 0 9 0 3 5 5 8 3 1 5 0 
----------------------------------------------------
    1 1 6 7 6 2 8 1 3 5 6 2 8 4 3 5 5 4 4 5


 完整代码：

[java] view plaincopyprint?在CODE上查看代码片派生到我的代码片
 
  1. import java.util.Random;  
  2. public class Sub{  
  3.       
  4.       
  5.       
  6.     //判别大小  
  7.     public Boolean compare(int[] a,int[] b){  
  8.         Boolean bool=true;//大于  
  9.         for(int i=0;i<a.length;i++){  
  10.             //从高位开始遍历  
  11.             if(a[i]<b[i]){  
  12.                 bool=false;  
  13.                 break;  
  14.             }  
  15.             else if(a[i]>b[i]){  
  16.                 bool=true;  
  17.                 break;  
  18.             }  
  19.         }  
  20.         return bool;  
  21.     }  
  22.       
  23.       
  24.       
  25.     public int[] subtraction(int[] a,int[] b){  
  26.         int[] c=new int[a.length];  
  27.         //a[0]...a[n]代表高位到低位  
  28.         for(int i=c.length-1;i>=0;i--){  
  29.             //最高位不借位  
  30.             if(i!=0){  
  31.                     if(a[i]<b[i]){  
  32.                         a[i-1]-=1;//向高位借位  
  33.                         a[i]+=10;  
  34.                     }     
  35.             }  
  36.             c[i]=a[i]-b[i];//存储对应位的差值  
  37.         }  
  38.         return c;  
  39.     }  
  40.     //输出  
  41.     public void print(int[] bt){  
  42.         for(int b : bt){  
  43.             System.out.print(b+" ");  
  44.       }  
  45.         
  46.        
  47.     }  
  48.       
  49.     public static void main(String[] args){  
  50.           
  51.         Random rand=new Random();  
  52.         for(int i=0;i<5;i++){  
  53.             Sub sub=new Sub();  
  54.             int[] a=new int[20];  
  55.             int[] b=new int[20];  
  56.             for (int n=0; n<a.length; n++) {  
  57.                 a[n]=rand.nextInt(10);//随机0--9  
  58.                 b[n]=rand.nextInt(10);  
  59.             }   
  60.             System.out.print("    ");  
  61.             sub.print(a);  
  62.             System.out.println("");  
  63.             System.out.print("-   ");  
  64.             sub.print(b);  
  65.             System.out.println("");  
  66.             System.out.println("------------------------------------------------");  
  67.             if(sub.compare(a,b)){//保证被减数大于减数  
  68.                 System.out.print("    ");  
  69.                 sub.print(sub.subtraction(a,b));  
  70.                 System.out.println("");  
  71.             }  
  72.             else{  
  73.                 System.out.print("   -");  
  74.                 sub.print(sub.subtraction(b,a));  
  75.                 System.out.println("");  
  76.             }  
  77.                  System.out.println("");  
  78.                  System.out.println("");  
  79.         }  
  80.                   
  81.                   
  82.            
  83.     }  
  84. }  


 

 7.上海华为的一道关于指针方面的编程题

题目：

     int A[nSize]，其中隐藏着若干0，其余非0整数，写一个函数int Func(int* A, int nSize)，使A把0移至后面，非0整数移至 数组前面并保持有序，返回值为原数据中第一个元素为0的下标。(尽可能不使用辅助空间且考虑效率及异常问题，注释规范且给出设计思路)

思路：
     选择一个排序算法对其进行排序，在排序过程中记录0元素的个数count，即nSize-count为首个0元素的下标；需要注意的是，若排序时需由大到小的排序（题中只说保持有序），不然0元素出现在前半部分又要移动元素。

 C实现如下：

[cpp] view plaincopyprint?在CODE上查看代码片派生到我的代码片
 
  1. #include <stdio.h>  
  2. using namespace std;  
  3. int Func(int *A,int nSize){  
  4.     if(A!=0&&nSize>0){  
  5.         int count=0;//记录0元素的个数  
  6.         //折半插入排序  
  7.         int low,high,mid;  
  8.         if(*A==0)  
  9.             count++;  
  10.         for(int i=1;i<nSize;i++){  
  11.             low=0;  
  12.             high=i-1;  
  13.             mid=(low+high)/2;  
  14.             while(low<=high){  
  15.                 if(*(A+i)>*(A+mid))//key>mid  
  16.                     high=mid-1;//注意此处故意倒序排列  
  17.                 else  
  18.                     low=mid+1;  
  19.                 mid=(low+high)/2;  
  20.             }  
  21.             //high+1为待插入位置  
  22.             int key=*(A+i);  
  23.             //后移元素腾出位置  
  24.             for(int j=i;j>high+1;j--){  
  25.                 *(A+j)=*(A+j-1);  
  26.             }  
  27.             *(A+high+1)=key;//插入  
  28.   
  29.             if(key==0)  
  30.                 count++;  
  31.         }  
  32.         return nSize-count;  
  33.     }  
  34.     else  
  35.         return -1;  
  36. }  
  37.   
  38. void main(){  
  39.     int a[]={0,3,0,4,9,1,0,44,2,0,12};  
  40.     int index=Func(a,11);  
  41.     printf("首个0在 %d 处 ",index);  
  42.     for(int i=0;i<11;i++){  
  43.         printf("%d ",a[i]);  
  44.     }  
  45. }  

输出：

首个0在 7 处
44 12 9 4 3 2 1 0 0 0 0 请按任意键继续. . .

8.素数问题

题目：
     求2~2000的所有素数.有足够的内存,要求尽量快
思路：
     查表法，即为2~2000的序列建立对应的表，表大小与序列大小一致(序列需要由小到大排序)，选择最小的素数并将其倍数剔除(在表中记录),在剩余的序列中，继续选择最小的素数并剔除其倍数，直到剔除到第N个。这样的好处在于每次遍历时可以参考上次table中的标记，可以避免许多重复操作。
     例如在判断4是否为素数时，由于在剔除2的倍数时在表中已经标记为NONPRIME（不是素数），那就不比调用判断素数的方法，省去许多操作。

C实现，为了输出方便，选择10以内的素数

[cpp] view plaincopyprint?在CODE上查看代码片派生到我的代码片
 
  1. #include <stdio.h>  
  2. #include <math.h>  
  3. #define TRUE 1  
  4. #define FALSE 0  
  5. #define NULL -1   //未遍历标记  
  6. #define NONPRIME 0//不是素数标记  
  7. #define PRIME 1   //是素数标记  
  8. #define LEN 10+1  //为了让数组下标一致  
  9. using namespace std;  
  10.   
  11. int isPrime(int num){  
  12.     if(num==2)  
  13.         return TRUE;  
  14.     for(int i=2;i<=sqrt((double)num);i++){  
  15.         if(num%i==0)  
  16.             return FALSE;  
  17.     }  
  18.     return TRUE;  
  19. }  
  20. //将num的倍数剔除（num为最小质数）  
  21. void deleNonPrime(int table[], int num){  
  22.     table[num]=PRIME;  
  23.     for(int i=2*num;i<LEN;i+=num){  
  24.           
  25.         if(table[i]==NULL){//有可能已经被赋值了  
  26.            table[i]=NONPRIME;  
  27.         }  
  28.     }  
  29. }  
  30.   
  31. void print(int arr[],int size){  
  32.     for(int i=2;i<size;i++){  
  33.         printf("%d ",arr[i]);  
  34.     }  
  35.     printf(" ");  
  36.   
  37. }  
  38.   
  39. void main(){  
  40.     int primes[LEN]={NULL};  
  41.     int table[LEN]={NULL};//建立对应的表  
  42.     for(int i=2;i<LEN;i++){  
  43.         primes[i]=i;  
  44.         table[i]=NULL;  
  45.     }  
  46.     for(int j=2;j<LEN;j++){  
  47.         if(j==2){  
  48.             deleNonPrime(table,2);  
  49.         }  
  50.         else{//参考上次表中的标记  
  51.             if(table[j]==NULL){//有可能为素数（剔除时有可能已经判断过了，避免重复判断）  
  52.                 if(isPrime(primes[j])){  
  53.                     deleNonPrime(table,primes[j]);  
  54.                 }  
  55.             }  
  56.         }  
  57.         printf("序列：");  
  58.         print(primes,LEN);  
  59.         printf("  表：");  
  60.         print(table,LEN);  
  61.         printf(" ");  
  62.   
  63.     }  
  64.     for(int i=2;i<LEN;i++){  
  65.         if(table[i]==PRIME)  
  66.           printf("%d ",i);  
  67.     }  
  68.   
  69. }  


输出：

序列：2 3 4 5 6 7 8 9 10
  表：1 -1 0 -1 0 -1 0 -1 0


序列：2 3 4 5 6 7 8 9 10
  表：1 1 0 -1 0 -1 0 0 0


序列：2 3 4 5 6 7 8 9 10
  表：1 1 0 -1 0 -1 0 0 0


序列：2 3 4 5 6 7 8 9 10
  表：1 1 0 1 0 -1 0 0 0


序列：2 3 4 5 6 7 8 9 10
  表：1 1 0 1 0 -1 0 0 0


序列：2 3 4 5 6 7 8 9 10
  表：1 1 0 1 0 1 0 0 0


序列：2 3 4 5 6 7 8 9 10
  表：1 1 0 1 0 1 0 0 0


序列：2 3 4 5 6 7 8 9 10
  表：1 1 0 1 0 1 0 0 0


序列：2 3 4 5 6 7 8 9 10
  表：1 1 0 1 0 1 0 0 0


2 3 5 7 请按任意键继续. . .

注意isPrime函数判断素数时只用判断至sqrt处(素数定理)。

9.操作系统任务调度问题

题目：

     操作系统任务分为系统任务和用户任务两种。其中，系统任务的优先级 < 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[])

思路：

     先以50做为关键字对原有序列进行一次快排，返回50的待插入位置location即为系统任务的个数，然后以location做为分界线，左右两边分别进行快排，最后依次将左半部放在system_task[]中，右半部分放在user_task[]（需剔除大于255的）

C/C++实现如下：

[cpp] view plaincopyprint?在CODE上查看代码片派生到我的代码片
 
  1. #include <stdio.h>  
  2. using namespace std;  
  3. // 利用一趟快速排序找分界线的位置i,即[low,i)为系统任务，[i,high]为用户任务  
  4. int findLine(int task[],int lowSpace,int highSpace,int key){  
  5.     int low=lowSpace,high=highSpace;  
  6.     while(low<high){  
  7.       
  8.         while(low<high&&task[high]>key){  
  9.             high--;  
  10.         }  
  11.         if(low<high){  
  12.             int tmp=task[high];  
  13.             task[high]=task[low];  
  14.             task[low]=tmp;  
  15.         }  
  16.         while(low<high&&task[low]<key){  
  17.             low++;  
  18.         }  
  19.         if(low<high){  
  20.             int tmp=task[low];  
  21.             task[low]=task[high];  
  22.             task[high]=tmp;  
  23.         }  
  24.           
  25.     }  
  26.     return low;  
  27.      
  28. }  
  29.   
  30. void quickSort(int subTask[],int lowSpace,int highSpace){  
  31.       
  32.     if(lowSpace<highSpace){//限制递归  
  33.         int low=lowSpace,high=highSpace;  
  34.         int insertIndex;//待插入位置  
  35.         int key=subTask[lowSpace];//关键字  
  36.         while(low<high){  
  37.       
  38.             while(low<high&&subTask[high]>=key){  
  39.                 high--;  
  40.             }  
  41.             if(low<high){  
  42.                 int tmp=subTask[high];  
  43.                 subTask[high]=subTask[low];  
  44.                 subTask[low]=tmp;  
  45.             }  
  46.             while(low<high&&subTask[low]<=key){  
  47.                 low++;  
  48.             }  
  49.             if(low<high){  
  50.                 int tmp=subTask[low];  
  51.                 subTask[low]=subTask[high];  
  52.                 subTask[high]=tmp;  
  53.             }  
  54.           
  55.         }  
  56.         insertIndex=low;  
  57.         subTask[insertIndex]=key;  
  58.         if(insertIndex==lowSpace)  
  59.             quickSort(subTask,insertIndex+1,highSpace);//只用排高区  
  60.         else if(insertIndex==highSpace)  
  61.             quickSort(subTask,lowSpace,insertIndex-1);//只用排低区  
  62.         else {  
  63.             quickSort(subTask,lowSpace,insertIndex-1);  
  64.             quickSort(subTask,insertIndex+1,highSpace);  
  65.         }  
  66.     }  
  67. }  
  68.   
  69. void scheduler(int task[], int n, int system_task[], int user_task[]){  
  70.     int index=findLine(task,0,n-1,50);//以50为关键字划分  
  71.     //分别排序  
  72.     quickSort(task,0,index);  
  73.     quickSort(task,index+1,n-1);  
  74.     int len=0;//记录用户任务的长度,因为需要剔除大于255的数，所以长度不一定为n-index  
  75.     for(int i=0;i<n;i++){  
  76.         //系统任务[0,index)  
  77.         if(i<=index){  
  78.             system_task[i]=i;  
  79.         }  
  80.         //用户任务[index,n)  
  81.         else if(i>index){  
  82.             //剔除无效任务  
  83.              if(task[i]>=50&&task[i]<=255){  
  84.                 user_task[i-index-1]=i;  
  85.                 len++;  
  86.              }  
  87.               
  88.   
  89.         }  
  90.           
  91.           
  92.     }  
  93.     system_task[index+1]=-1;//结束  
  94.     user_task[len]=-1;  
  95.   
  96.   
  97. }  
  98.   
  99. void printArr(int task[],int n){  
  100.     for(int i=0;i<n;i++){  
  101.       printf("%d ",task[i]);  
  102.     }  
  103.     printf(" ");  
  104. }  
  105. //测试  
  106. void main(){  
  107.     int task[]={0, 30, 155, 1, 80, 300, 170, 40, 99};  
  108.     int system_task[9]={-1};  
  109.     int user_task[9]={-1};  
  110.     scheduler(task,9,system_task,user_task);  
  111.     printf("排序完成后总任务为： ");  
  112.     printArr(task,9);  
  113.     printf("系统任务为： ");  
  114.     printArr(system_task,9);  
  115.     printf("用户任务为： ");  
  116.     printArr(user_task,9);  
  117. }  


输出：

排序完成后总任务为：
0 1 30 40 80 99 155 170 300
系统任务为：
0 1 2 3 -1 0 0 0 0
用户任务为：
4 5 6 7 -1 0 0 0 0
请按任意键继续. . .

    突然发现自己把题意弄错了，我虽然实现了任务分离和任务，但是题目输出的是原始索引坐标，并不是排序后的。为了实现寻找原始索引，引入一个索引表，只要任务元素被移动，则table的索引随之移动，最后只要查表即可。

C#实现如下：

[csharp] view plaincopyprint?在CODE上查看代码片派生到我的代码片
 
  1. using System;  
  2. using System.Collections.Generic;  
  3. using System.Linq;  
  4. using System.Text;  
  5.   
  6. namespace 控制台编程练习  
  7. {  
  8.     class 任务分配  
  9.     {  
  10.     //寻找关键字的分界线  
  11.     int findLine(int[] task,int lowSpace,int highSpace,int key,int[] table){  
  12.         int low=lowSpace,high=highSpace;  
  13.         while(low<high){  
  14.       
  15.             while(low<high&&task[high]>key){  
  16.                 high--;  
  17.             }  
  18.             if(low<high){  
  19.                 swap(high, low, task);  
  20.                 swap(high, low, table);  
  21.             }  
  22.             while(low<high&&task[low]<key){  
  23.                 low++;  
  24.             }  
  25.             if(low<high){  
  26.                 swap( low,high ,task);  
  27.                 swap(low, high, table);  
  28.             }  
  29.           
  30.         }  
  31.         return low;  
  32.      
  33. }  
  34. //交换  
  35. void swap(int a,int b,int[] task){  
  36.     int tmp= task[a];  
  37.     task[a]=task[b];  
  38.     task[b]=tmp;  
  39. }  
  40. //快排  
  41. void quickSort(int[] subTask,int lowSpace,int highSpace,int[] index){  
  42.       
  43.     if(lowSpace<highSpace){//限制递归  
  44.         int low=lowSpace,high=highSpace;  
  45.         int insertIndex;//待插入位置  
  46.         int key=subTask[lowSpace];//关键字  
  47.         int table_key = index[lowSpace];//表索引虚拟关键字  
  48.         while(low<high){  
  49.       
  50.             while(low<high&&subTask[high]>=key){  
  51.                 high--;  
  52.             }  
  53.             if(low<high){  
  54.                 swap(high,low,subTask);  
  55.                 swap(high,low,index);  
  56.             }  
  57.             while(low<high&&subTask[low]<=key){  
  58.                 low++;  
  59.             }  
  60.             if(low<high){  
  61.                 swap(low,high,subTask);  
  62.                 swap(low,high,index);  
  63.             }  
  64.           
  65.         }  
  66.         insertIndex=low;  
  67.         subTask[insertIndex]=key;  
  68.         index[insertIndex]=table_key;//索引表也要变动  
  69.         if(insertIndex==lowSpace)  
  70.             quickSort(subTask,insertIndex+1,highSpace,index);//只用排高区  
  71.         else if(insertIndex==highSpace)  
  72.             quickSort(subTask,lowSpace,insertIndex-1,index);//只用排低区  
  73.         else {  
  74.             quickSort(subTask,lowSpace,insertIndex-1,index);  
  75.             quickSort(subTask,insertIndex+1,highSpace,index);  
  76.         }  
  77.     }  
  78. }  
  79. //建立索引表  
  80. int[] creatTable(int n)  
  81. {  
  82.     int[] table = new int[n];  
  83.     for (int i = 0; i < n; i++)  
  84.     {  
  85.         table[i] = i;  
  86.     }  
  87.     return table;  
  88. }  
  89.   
  90. void scheduler(int[] task, int n, int[] system_task, int[] user_task){  
  91.     int[] table = creatTable(n);  
  92.     int index = findLine(task, 0, n - 1, 50, table);//以50为关键字划分  
  93.     //分别排序  
  94.     quickSort(task,0,index,table);  
  95.     quickSort(task,index+1,n-1,table);  
  96.     int len=0;//记录用户任务的长度,因为需要剔除大于255的数，所以长度不一定为n-index  
  97.     for(int i=0;i<n;i++){  
  98.         //系统任务[0,index)  
  99.         if(i<=index){  
  100.             system_task[i]=table[i];  
  101.         }  
  102.         //用户任务[index,n)  
  103.         else if(i>index){  
  104.             //剔除无效任务  
  105.              if(task[i]>=50&&task[i]<=255){  
  106.                 user_task[i-index-1]=table[i];  
  107.                 len++;  
  108.              }  
  109.         }  
  110.     }  
  111.     system_task[index+1]=-1;//结束  
  112.     user_task[len]=-1;  
  113. }  
  114.   
  115. void printArr(int[] task,int n){  
  116.     for(int i=0;i<n;i++){  
  117.       Console.Write(task[i]+" ");  
  118.     }  
  119.     Console.WriteLine();  
  120. }  
  121.   
  122.     static void Main()  
  123.     {  
  124.         任务分配 s = new 任务分配();  
  125.         int[] task={0, 30, 155, 1, 80, 300, 170, 40, 99};  
  126.         int[] system_task=new int[9];  
  127.         int[] user_task=new int[9];  
  128.         Console.WriteLine("原始任务为:");  
  129.         s.printArr(task,9);  
  130.         s.scheduler(task, 9, system_task, user_task);  
  131.         Console.WriteLine("系统任务为:");  
  132.         s.printArr(system_task, 9);  
  133.         Console.WriteLine("用户任务为:");  
  134.         s.printArr(user_task, 9);  
  135.     }  
  136.   }  
  137. }  


输出：

原始任务为:
0 30 155 1 80 300 170 40 99
系统任务为:
0 3 1 7 -1 0 0 0 0
用户任务为:
4 8 2 6 -1 0 0 0 0
请按任意键继续. . .

10.奇偶插入排序

题目：
     对一个数组，将数组中偶数从大到小排序，奇数从小到大排序,奇数和偶数交叉着放且输出数组第一位放奇数若奇数和偶数不等长，则把剩下的直接放到数组中。
思路：
     将奇数和偶数元素分别存放，然后分别排序，最后一起交叉填充(覆盖)到原数组。

C/C++实现如下：

 
 

[cpp] view plaincopyprint?在CODE上查看代码片派生到我的代码片
 
  1. #include<stdio.h>  
  2. #include<malloc.h>  
  3. #define DEFAULT 0  
  4. #define low_to_high 0//由小到大  
  5. #define high_to_low 1//由大到小  
  6. using namespace std;  
  7.   
  8. //折半插入排序  
  9. void halfSort(int *a,int n,int type){  
  10.     for(int i=1;i<n;i++){  
  11.         int high=i-1;  
  12.         int low=0;  
  13.         int mid=(high+low)/2;  
  14.         int key=a[i];//待排关键字  
  15.         //寻找位置  
  16.         if(type==low_to_high){  
  17.             while(low<=high){  
  18.                 if(a[mid]<key)  
  19.                     low=mid+1;  
  20.                 else  
  21.                     high=mid-1;  
  22.                 mid=(low+high)/2;  
  23.             }  
  24.         }  
  25.         else{  
  26.             while(low<=high){  
  27.                 if(a[mid]<key)  
  28.                     high=mid-1;  
  29.                 else  
  30.                     low=mid+1;  
  31.                 mid=(low+high)/2;  
  32.             }  
  33.         }  
  34.         //插入位置在high+1，全体移动a[high+1]...a[i]  
  35.         for(int j=i;j>high+1;j--){  
  36.             a[j]=a[j-1];  
  37.         }  
  38.         a[high+1]=key;  
  39.     }  
  40. }  
  41.   
  42. void print(int *a,int n){  
  43.     for(int i=0;i<n;i++){  
  44.         printf("%d ",*(a+i));  
  45.     }  
  46.     /*while(*a!=''){ 
  47.         printf("%d ",*a++); 
  48.     }*/  
  49.     printf(" ");  
  50. }  
  51.   
  52.   
  53. void oddAndEvenSort(int a[],int n){  
  54.     int odd[10]={0};  
  55.     int even[10]={0};  
  56.     int evenCount=0;//偶数个数  
  57.     int oddCount=0;  
  58.     for(int i=0;i<n;i++){  
  59.         if(a[i]%2==0){  
  60.             even[evenCount]=a[i];  
  61.           
  62.             evenCount++;  
  63.         }  
  64.         else{  
  65.             odd[oddCount]=a[i];  
  66.               
  67.             oddCount++;  
  68.         }  
  69.     }  
  70.       
  71.     halfSort(odd,oddCount,low_to_high);  
  72.     halfSort(even,evenCount,high_to_low);  
  73.     if(oddCount==0){  
  74.         print(even,evenCount);  
  75.     }  
  76.     else if(evenCount==0){  
  77.         print(odd,oddCount);  
  78.     }  
  79.     else if(oddCount<evenCount){  
  80.         for(int i=0;i<oddCount;i++){  
  81.             a[2*i]=odd[i];  
  82.             a[2*i+1]=even[i];  
  83.         }  
  84.         for(int j=oddCount;j<n;j++){//剩余偶数补全  
  85.             a[j+oddCount]=even[j];  
  86.         }  
  87.         print(a,n);  
  88.     }  
  89.     else if(oddCount==evenCount){  
  90.         for(int i=0;i<oddCount;i++){  
  91.             a[2*i]=odd[i];  
  92.             a[2*i+1]=even[i];  
  93.         }  
  94.         print(a,n);  
  95.     }  
  96.           
  97.     else if(oddCount>evenCount){  
  98.         for(int i=0;i<evenCount;i++){  
  99.             a[2*i]=odd[i];  
  100.             a[2*i+1]=even[i];  
  101.         }  
  102.         for(int j=evenCount;j<n;j++){//剩余奇数补全  
  103.             a[j+evenCount]=odd[j];  
  104.         }  
  105.         print(a,n);  
  106.     }  
  107.   
  108.   
  109. }  
  110.   
  111. void main(){  
  112.     int a1[]={2,4,6,8,10,12,14,16,18,1};  
  113.     oddAndEvenSort(a1,10);  
  114.     int a2[]={2,4,6,8,10,1,3,5,7,9};  
  115.     oddAndEvenSort(a2,10);  
  116.     int a3[]={2,4,6,1,3,5,7,9,11,13};  
  117.     oddAndEvenSort(a3,10);  
  118.   
  119. }  


 

输出：

1 18 16 14 12 10 8 6 4 2
1 10 3 8 5 6 7 4 9 2
1 6 3 4 5 2 7 9 11 13

总结：又没仔细看题，偶数元素是从大到小，奇数是从小到大排序，题目虽简，但也须仔细认真，切记。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/qxzy/p/4222561.html