[关闭]
@yudesong 2017-06-24T16:18:56.000000Z 字数 4547 阅读 616

经典算法题

经典算法题

1. 经典迷宫问题

给定一个迷宫，入口为左上角，出口为右下角，问是否有路径从入口到出口，若有则输出一条这样的路径。注意移动可以从上、下、左、右、上左、上右、下左、下右八个方向进行。迷宫输入0表示可走，输入1表示墙。易得可以用1将迷宫围起来避免边界问题。

参考代码：

  1. #include <stdio.h>
  3. int visit(int i , int j);
  5. int maze[7][7] = {
  6.         {2,2,2,2,2,2,2},
  7.         {2,0,0,0,0,0,2},
  8.         {2,0,2,0,2,0,2},
  9.         {2,0,0,2,0,2,2},
  10.         {2,2,0,2,0,2,2},
  11.         {2,0,0,0,0,0,2},
  12.         {2,2,2,2,2,2,2},
  13.     };
  14. int si = 1 , sj = 1 ;
  15. int ei = 5 , ej = 5 ;
  16. int success = 0 ;
  18. int main()
  19. {
  20.     int i , j ;
  21.     printf("Display the maze :\n");
  22.     for(i = 0 ; i < 7 ; i++)
  23.     {
  24.         for(j = 0 ; j < 7 ; j++)
  25.         {
  26.             if(maze[i][j] == 2)
  27.             {
  28.                 printf("■");
  29.             }
  30.             else
  31.             {
  32.                 printf("  ");
  33.             }
  34.         }
  35.         printf("\n");
  36.     }
  38.     if(visit(si , sj) == 0)
  39.     {
  40.         printf("\nNot found exit !");
  41.     }
  42.     else
  43.     {
  44.         printf("Display the maze :\n");
  45.         for(i = 0 ; i < 7 ; i++)
  46.         {
  47.             for(j = 0 ; j < 7 ; j++)
  48.             {
  49.                 if(maze[i][j] == 2)
  50.                 {
  51.                     printf("■");
  52.                 }
  53.                 else if(maze[i][j] == 1)
  54.                 {
  55.                     printf("◇");
  56.                 }
  57.                 else 
  58.                 {
  59.                     printf("  ");
  60.                 }
  61.             }
  62.             printf("\n");
  63.         }
  64.     }
  65. 　　 return 0 ;
  66. }
  68. int visit(int i , int j)
  69. {
  70.     maze[i][j] = 1 ;
  72.     if(i == ei && j == ej)
  73.     success = 1 ;
  75.     if(success != 1 && maze[i][j + 1] == 0) 
  76.     visit(i , j + 1);
  77.     if(success != 1 && maze[i + 1][j] == 0)
  78.     visit(i + 1 , j);
  79.     if(success != 1 && maze[i - 1][j] == 0)
  80.     visit(i - 1 , j);
  81.     if(success != 1 && maze[i][j - 1] == 0)
  82.     visit(i , j - 1);
  84.     if(success != 1)
  85.     maze[i][j] == 0 ;
  87.     return success ;
  88. }
2. 大数相乘问题
  1. void reverseOrder(char* str, int p, int q)
  2. {
  3.     char temp;
  4.     while(p < q)
  5.     {
  6.         temp = str[p];
  7.         str[p] = str[q];
  8.         str[q] = temp;
  9.         p ++;
  10.         q --;
  11.     }
  12. }
  14. char* multiLargeNum(char* A, char* B)
  15. {
  16.     int m = strlen(A);
  17.     int n = strlen(B);
  18.     char* result = new char[m+n+1];
  19.     memset(result, '0', m+n);
  20.     result[m+n] = '\0';
  21.     reverseOrder(A, 0, m-1);
  22.     reverseOrder(B, 0, n-1);
  24.     int multiFlag; // 乘积进位
  25.     int addFlag;   // 加法进位
  26.     for(int i=0; i <= n-1; i++) // B的每一位
  27.     {
  28.         multiFlag = 0;
  29.         addFlag = 0;
  30.         for(int j=0; j <= m-1; j++) // A的每一位
  31.         {
  32.             // '0' - 48 = 0
  33.             int temp1 = (A[j] - 48) * (B[i] - 48) + multiFlag;
  34.             multiFlag = temp1 / 10;
  35.             temp1 = temp1 % 10;
  36.             int temp2 = (result[i+j] - 48) + temp1 + addFlag;
  37.             addFlag = temp2 / 10;
  38.             result[i+j] = temp2 % 10 + 48; 
  39.         }
  40.         result[i + m] += multiFlag + addFlag;
  41.     }
  42.     reverseOrder(result, 0, m+n-1); // 逆序回来
  44.     return result;
  45. }
  47. int main()
  48. {
  49.     char A[] = "962346239843253528686293234124";
  50.     char B[] = "93459382645998213649236498";
  51.     char *res = multiLargeNum(A, B);
  52.     if(res[0] != 48)
  53.         printf("%c", res[0]);
  54.     printf("%s", res+1);
  55.     delete [] res;
  56.     return 0;
  57. }
3. 大数相加
  1. #include<stdio.h>
  2. #include<string.h>
  3. #define Max 101
  4. void print(char sum[]);
  5. void bigNumAdd(char a[],char b[],char sum[]);
  6. int main()
  7. {
  8.     char a[Max];
  9.     char b[Max];
  10.     char sum[Max];
  11.     gets(a);
  12.     gets(b);
  13.     bigNumAdd(a,b,sum);
  14.     print(sum);
  15.     return 0;
  16. }
  18. void bigNumAdd(char a[],char b[],char sum[])
  19. {
  20.     int i=0;
  21.     int c=0;//表示进位
  22.           //初始化,对以后位运算有很大帮助！
  23.     char m[Max]={0};
  24.     char n[Max]={0};
  25.     memset(sum,0,Max*sizeof(char)); //这里不能写成memset(sum,0,sizeof(sum));原因见注意事项1
  26.     //字符串反转且字符串变数字
  27.     int lenA=strlen(a);
  28.     int lenB=strlen(b);
  29.     for (i=0;i<lenA;i++)
  30.     {
  31.         m[i]=a[lenA-i-1]-'0';
  32.     }
  33.     for (i=0;i<lenB;i++)
  34.     {
  35.         n[i]=b[lenB-i-1]-'0';
  36.     }
  37.     //位运算
  38.     for (i=0;i<lenA||i<lenB;i++)
  39.     {
  40.         sum[i]=(m[i]+n[i]+c)%10+'0';//得到末位
  41.         c=(m[i]+n[i]+c)/10;//得到进位
  42.     }
  43. }
  45. void print(char sum[])
  46. {
  47.     int i=0;
  48.     int j=0;
  49.     int len = strlen(sum);
  50.     for (i=len-1;sum[i]==0;i--); //找到第一个不为零的位置，方便输出
  51.     for (j=i;j>=0;j--)
  52.     {
  53.         printf("%c",sum[j]);
  54.     }
  55. }
4. 八皇后问题
  1. #include <iostream>
  2. #include <math.h>
  3. using namespace std;
  4. const int N=20;
  5. int q[N];
  6. int count=0;
  7. void display()
  8. {
  9.     count++;
  10.     int i;
  11.     for(i=1;i<=6;i++)
  12.         cout<<q[i]<<" ";
  13.     cout<<endl;    
  14. }
  16. bool find(int i,int j)
  17. {
  18.     int m=1;
  19.     while(m<j)
  20.     {
  21.         if((q[m]==i) || abs(q[m]-i)==abs(m-j))
  22.         return false;
  23.         m++;
  24.     }
  25.     return true;
  26. }
  28. void place(int i,int n)
  29. {
  30.     if(i>n) display();
  31.     else
  32.     {
  33.         int j;
  34.         for(j=1;j<=n;j++) 
  35.         {
  36.             if(find(j,i))
  37.             {
  38.                 q[i]=j;
  39.                 place(i+1,n);
  40.             }
  41.         }    
  42.     }
  43. }
  45. int main()
  46. {
  47.     place(1,6);
  48.     return 0;    
  49. }
5. 旅行商问题
  1. #include<iostream>
  2. #include<iomanip>
  3. using namespace std;
  5. int n;
  6. int cost[20][20]={};
  7. bool done[20]={1};
  8. int start = 0; //从城市0开始
  10. int imin(int num, int cur)
  11. {
  12.     if(num==1) //递归调用的出口
  13.         return cost[cur][start];  
  14.        //所有节点的最后一个节点，最后返回 最后一个节点到起点的路径
  16.     int mincost = 10000;
  17.     for(int i=0; i<n; i++)
  18.     {
  19.         cout<<i<<"  i:"<<done[i]<<endl; 
  20.         if(!done[i] && i!=start) //该结点没加入 且 非起始点 
  21.         {
  22.             if(mincost <= cost[cur][i]+cost[i][start])
  23.             {
  24.                 continue; 
  25. //其作用为结束本次循环。即跳出循环体中下面尚未执行的语句。区别于break 
  26.             }
  27.             done[i] = 1; //递归调用时，防止重复调用
  29.             int value = cost[cur][i] + imin(num-1, i);
  31.             if(mincost > value)
  32.             {
  33.                 mincost = value;
  34.             }
  35.             done[i] = 0;//本次递归调用完毕，让下次递归调用
  36.         }
  37.     }
  38.     return mincost;
  39. }
  41. int main()
  42. {
  43. //  cin >> n;
  44.     n=4;
  45.     int cc[4][4]={{0 ,4, 1, 3},
  46.                {4 ,0 ,2, 1},
  47.                 {1 ,2 ,0, 5},
  48.                    {3 ,1, 5, 0}};
  49.     for(int i=0; i<n; i++)
  50.     {
  51.         for(int j=0; j<n; j++)
  52.         {
  53.             //cin >> cost[i][j];
  54.             cost[i][j]=cc[i][j];
  55.         }
  56.     }
  57.     cout << imin(n, start) << endl;
  58.     return 0;
  59. }
6. 0/1背包问题
  1. int V[200][200];
  2. //前i个物品装入容量为j的背包中获得的最大价值
  3. int max(int a,int b)
  4. {
  5.    if(a>=b)
  6.        return a;
  7.    else return b;
  8. }
  10. int KnapSack(int n,int w[],int v[],int x[],int C)
  11. {
  12.     int i,j;
  13.     for(i=0;i<=n;i++)
  14.         V[i][0]=0;
  15.     for(j=0;j<=C;j++)
  16.         V[0][j]=0;
  17.     for(i=0;i<=n-1;i++)
  18.         for(j=0;j<=C;j++)
  19.             if(j<w[i])
  20.                 V[i][j]=V[i-1][j];
  21.             else
  22.                 V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);
  23.             j=C;
  24.             for(i=n-1;i>=0;i--)
  25.             {
  26.                 if(V[i][j]>V[i-1][j])
  27.                 {
  28.                 x[i]=1;
  29.                 j=j-w[i];
  30.                 }
  31.             else
  32.                 x[i]=0;
  33.             }
  34.             printf("选中的物品是:\n");
  35.             for(i=0;i<n;i++)
  36.                 printf("%d ",x[i]);
  37.             printf("\n");
  38.         return V[n-1][C];
  40. }
  42. void main()
  43. {
  44.     int s;//获得的最大价值
  45.     int w[15];//物品的重量
  46.     int v[15];//物品的价值
  47.     int x[15];//物品的选取状态
  48.     int n,i;
  49.     int C;//背包最大容量
  50.     n=5;
  51.     printf("请输入背包的最大容量:\n");
  52.     scanf("%d",&C);
  54.     printf("输入物品数:\n");
  55.     scanf("%d",&n);
  56.     printf("请分别输入物品的重量:\n");
  57.     for(i=0;i<n;i++)
  58.         scanf("%d",&w[i]);
  60.     printf("请分别输入物品的价值:\n");
  61.     for(i=0;i<n;i++)
  62.         scanf("%d",&v[i]);
  64.     s=KnapSack(n,w,v,x,C);
  66.     printf("最大物品价值为:\n");
  67.     printf("%d\n",s);
  68. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注