さいしょうブリッジじかん

元々は4人が橋を渡るのですが、ABCDは単独で橋を渡るにはそれぞれ1分、2分、5分、10分かかります.橋を渡るにはランプが必要です(1つしかありません)、一度に2人だけで渡ることができます(誰かが明かりを送って帰る必要があることを意味します)、橋を渡る時間が多くなった人は、どのように1つの案を設計して、使う時間を最小限に抑えることができます.
AとBは先に过ぎて、Aは帰って、CDは更に过ぎて、Bは帰って、ABは第2回过ぎます.17秒で完成!
C言語でn人になって橋を渡って、橋を渡る時間は自分で決めて、橋を渡る最も短い時間の方案を求めます.
まず、最小限の時間で橋を渡る問題を解決します.貪欲な方法をよく理解する:
1)人数<3の場合、直接
2)人数=3の場合,川を渡る時間が小さいから大きいa,b,c(後期配列の問題が解決しやすい)であると仮定し,明らかに最小でランプを送る(c+a+b
3)人数=4の場合,a,b,c,d(同様に昇順)
I最小で送る場合(最大の過去に合わせて、aが帰ってきて、また大きい過去に付き添って、帰ってくる):d+a+c+a+b=d+c+b+2 a
Ⅱ一番小さい二つの橋を渡って、その中の一つを返して、一番大きい二つの橋を渡って、それから前に残った二つの橋を返して、それから一番小さい二つの橋を渡します:b+a+d+b=d+3 b+a
d+c+b+2 a
4)人数>4のとき,a,b....c,d(昇順)は、最小のものを送る場合、d+a+c+a=d+c+2 aとし、最小の2つのブリッジb+b+a+d=d+2 b+aとする場合、c-2 b+a<=0の場合、第1の方法を用いる.
入力したデータは、クイックソートでソートできます(qsortの使用については、「VCライブラリ関数のクイックソート関数の使用」を参照してください).#include #define MAX 100 int CrossBridge( int a[], int n) {      int time ;      if (n==1)      {          time =a[0];          printf ( " -> :%d
" ,a[0]);          return time ;      }      else if (n==2)      {          time =a[1];          printf ( " -> :%d,%d
" ,a[0],a[1]);          return time ;      }      else if (n==3)      {          time =a[0]+a[1]+a[2];          printf ( " -> :%d,%d
" ,a[2],a[0]);          printf ( " ->:%d
" ,a[0]);          printf ( " -> :%d,%d
" ,a[0],a[1]);          return time ;      }      else      {          if (2*a[1]>a[0]+a[n-2])          {              time =2*a[0]+a[n-1]+a[n-2];              printf ( " -> :%d,%d,
" ,a[n-1],a[0]);              printf ( " :%d
" ,a[0]);              printf ( " -> :%d,%d
" ,a[0],a[n-2]);              printf ( " :%d
" ,a[0]);          }          else          {              time =a[0]+a[1]+a[n-1]+a[1];              printf ( " -> :%d,%d
" ,a[0],a[1]);              printf ( " :%d
" ,a[0]);              printf ( " -> :%d,%d
" ,a[n-1],a[n-2]);              printf ( " :%d
" ,a[0]);          }          return time +CrossBridge(a,n-2);      } }     void sort( int b[], int n) {      int i,j,k,index,temp;      for (i=0;i      {          index=i;          for (j=i+1;j          {              if (b[index]>b[j])              index=j;          }          temp=b[i];          b[i]=b[index];          b[index]=temp;      }      for (k=0;k          printf ( "%-3d" ,b[k]); }     int main() {      int crossnum,i;      int t[MAX];      printf ( " n：" );      scanf ( "%d" ,&crossnum);      printf ( "
" );      for (i=0;i      {          scanf ( "%d" ,&t[i]);      }      printf ( " ：" );      sort(t,crossnum);      printf ( " :
" );      printf ( " %d :%d
" ,crossnum,CrossBridge(t,crossnum));      return 0; }