汽车加油站.cpp

一辆汽车加满油后可行使N公里

/*题目：一辆汽车加满油后可行使N公里，旅途中有若干个加油站，使沿途加油次数最少，设计一个有效算法，指出应在哪些加油站停靠加油。*/ 
/*贪心算法 */   
//   最优加油问题   
//   一辆汽车加满油后可行使N公里，旅途中有若干个加油站，若要使沿途加油次数   
//   最少，设计一个有效算法，指出应在哪些加油站停靠加油。   

  #pragma   hdrstop     
  #include   <stdio.h>      
  #define   MAX_DIST   5000       
  unsigned   distances[MAX_DIST];   
  unsigned   stops[MAX_DIST];   
  unsigned   N;           //   满油行驶里程   
  unsigned   cnt=0;   //   除了始发站外的加油站数目   
    
  void   check_stops()   
  {   
          unsigned   rc=N;   //   还可以走的里程数   
          unsigned   i;   
          for(i=0;   i<cnt-1;   i++){   
                  if(rc   <distances[i]+distances[i+1]){   
                          stops[i]   =   1;   
                          rc   =   N;   
                  }else{   
                          stops[i]   =   0;   
                          rc   -=   distances[i];   
                  }   
          }   
  }   
    
  void   report_stops()   
  {   
          unsigned   i;   
          printf("加油站的编号如下:\n");   
          for(i=0;   i<cnt-1;   i++)   
                  if(stops[i])   
                          printf("%u   ",   i+1);   
          printf("\n");   
  }   
    
  #pragma   argsused   
  int   main(int   argc,   char*   argv[])   
  {   
          int   i;   
          printf("请输入满油行驶公里数:");   
          scanf("%u",&N);   
          do{   
                  unsigned   distance;   
                  printf("输入到下一个加油站的公里数[0表示结束]:");   
                  scanf("%u",&distance);   
                  if(distance>N){   
                          printf("太远了!\n");   
                          continue;   
                  }   
                  if(distance   ==   0)   
                          break;   
                  distances[cnt++]   =   distance;   
          }while(cnt   <   MAX_DIST);   
    
          check_stops();   
          report_stops();   
          return   0;   
  }