经典指数          
原因
1406
浏览数
0
收藏数
 

一个酒吧内有排成一行的25个座位,到酒吧的客人都生性内向不擅交际,因此他们都会坐到离其他人最远的位置(即离最近的人最远),如果新进来的客人发现左右两边都有人没有空位的话就会离开。你做为老板希望客人越多越好,如果你可以安排第一个进来的客人坐什么地方,该怎么安排?

     举报   纠错  
 
切换
1 个答案
先说答案:第一个人坐在第9和17个位置最优。 首先我们找出最佳做法最后应该得到的座位情况: 人空人空人空人空人空人空人空人空人空人空人空人空人 也就是每两个人之间间隔一个空位。 然后需要去找能得出这个情况的所有第一个坐的位置,当我分析到第9和第17的时候,发现它们都具有递归效应,贪心的坐下去,最后都得到理想情况。 然后我用C++写了一个模拟的程序,得出来结果也是第一个人先坐第9个或者第17个位置最优。 程序输出: 第一个人坐在第 1 位能坐的人数 : 8 人空空人空空人空空人空空人空空人空空人空空人空空人 第一个人坐在第 2 位能坐的人数 : 8 空人空人空空人空空人空空人空空人空空人空空人空空人 第一个人坐在第 3 位能坐的人数 : 9 人空人空人空空人空空人空空人空人空空人空空人空空人 第一个人坐在第 4 位能坐的人数 : 9 人空空人空人空空人空人空空人空人空空人空空人空空人 第一个人坐在第 5 位能坐的人数 : 10 人空人空人空人空空人空人空空人空人空空人空人空空人 第一个人坐在第 6 位能坐的人数 : 10 人空人空空人空人空人空人空空人空人空空人空人空空人 第一个人坐在第 7 位能坐的人数 : 10 人空空人空空人空人空人空人空空人空人空人空人空空人 第一个人坐在第 8 位能坐的人数 : 11 人空空人空人空人空人空人空人空人空人空人空人空空人 第一个人坐在第 9 位能坐的人数 : 12 人空人空人空人空人空人空人空人空人空人空人空人空人 第一个人坐在第 10 位能坐的人数 : 11 人空人空人空人空空人空空人空人空人空人空人空人空人 第一个人坐在第 11 位能坐的人数 : 10 人空人空空人空人空空人空空人空人空人空空人空人空人 第一个人坐在第 12 位能坐的人数 : 9 人空人空空人空空人空空人空空人空空人空空人空人空人 第一个人坐在第 13 位能坐的人数 : 8 人空空人空空人空空人空空人空空人空空人空空人空空人 第一个人坐在第 14 位能坐的人数 : 9 人空空人空空人空空人空人空人空人空空人空空人空空人 第一个人坐在第 15 位能坐的人数 : 10 人空空人空人空人空空人空人空人空人空空人空人空空人 第一个人坐在第 16 位能坐的人数 : 11 人空空人空人空人空人空人空人空人空人空人空人空空人 第一个人坐在第 17 位能坐的人数 : 12 人空人空人空人空人空人空人空人空人空人空人空人空人 第一个人坐在第 18 位能坐的人数 : 11 人空人空人空人空人空人空人空人空空人空空人空人空人 第一个人坐在第 19 位能坐的人数 : 10 人空人空人空人空空人空人空人空人空空人空空人空空人 第一个人坐在第 20 位能坐的人数 : 10 人空人空人空人空空人空人空空人空人空空人空人空空人 第一个人坐在第 21 位能坐的人数 : 10 人空人空空人空人空空人空人空空人空人空空人空人空人 第一个人坐在第 22 位能坐的人数 : 9 人空人空空人空人空空人空人空空人空空人空空人空空人 第一个人坐在第 23 位能坐的人数 : 9 人空人空空人空空人空空人空人空空人空空人空空人空人 第一个人坐在第 24 位能坐的人数 : 8 人空人空空人空空人空空人空空人空空人空空人空空人空 第一个人坐在第 25 位能坐的人数 : 8 人空空人空空人空空人空空人空空人空空人空空人空空人 程序源代码: #include using namespace std; int main(void) {   int a[26], an[26];     int INF = 1000000;     for (int i = 1; i <= 25; i++) {         memset(a, 0, sizeof(a));         a[i] = 1;         int temp = 0;         while (true) {             int p, ans = 0;             for (int i = 1; i <= 25; i++) {                 if (!a[i]) {                     int s = 0, e = 0;                     for (int j = i - 1;; j--) {                         if (j == 0) {                             s = INF;                             break;                         }                         if (a[j]) break;                         s++;                     }                     for (int j = i + 1; ; j++) {                         if (j == 26) {                             e = INF;                             break;                         }                         if (a[j]) break;                         e++;                     }                     if (min(s, e) > ans) ans = min(s, e), p = i;                 }             }             if (!ans) break;             a[p] = 1;            // cout << p << endl;             temp++;         }         an[i] = temp;         cout << "第一个人坐在第" << i  << "位" << "能坐的人数: " << temp << endl;         if (i) {             for (int i = 1; i <26; i++) {                 cout << (a[i] ? "人" : "空") ;             }             cout << endl;       }     } }
 
切换
撰写答案