プログラミングの美しさ-エレベーターの問題-Javaバージョン
Beauty Programming Elevator Problem Java Version
オフィスビルのエレベーターの高層ビルでは、各階に人がいます。エレベーターは各階に1人しか停車できません。これはもっと面倒です。下の階（6階）の場合、エレベーターが1階から上がるたびに、エレベーターは1階でのみ停止し、すべての乗客が階段を目標レベルまで上昇します。 1階では、乗客一人ひとりが自分の階を選び、エレベーターが各階の人数に応じて停車する階を計算します。
Q：エレベータが駐車されている階は、エレベータを利用する乗客の階段数が最も少ないことを保証できます。
分析と解決策：
問題の本質は最適化問題です。まず、この問題に適した抽象モデルを見つけます。問題からわかるように、最終結果に影響を与える2つの要因があります。それは、乗客数と停止する必要のある目的階です。したがって、各フロアに到着した乗客の数を数え、分析を開始できます。
フロアに合計N階があり、エレベータがX階に停車し、i階に行く乗客の総数がTot [i]であるとすると、階段の総数は∑になります。Ni = 1Tot [i] *の値が最小です。
解決策1：
最初の選択肢は、単純な解決策を検討することです。
第1層からN層までのxを列挙し、エレベータがxレベルで停止した場合に乗客が登る層の数を計算することができます。これは最も直接的な方法です。
これには、計算を完了するために二重ループが必要です。時間計算量はO（N二）。
解決策2：解決策2：
さらに分析すると、エレベータがi階に駐車していると仮定すると、明らかに、すべての乗客が登らなければならない階段Yの数を計算できます。 i階下にN1の乗客がいる場合、i階にN2の乗客がいて、i階の上にN3の乗客がいます。このとき、i-1階に乗り換えると、i階以上の乗客は全員もう1階登る必要があります。合計で、彼らはより多くのN2 + N3フロアを登る必要があり、すべての目的地はi-1フロアにあります。以下の乗客は1階未満で登ることができ、合計で1階未満で登ることができます。したがって、乗客が合計で登る必要のある層の数は、Y-N1 +（N2 + N3）= Y-（N1-N2-N3）層です。
逆に、エレベータがi + 1階にある場合、乗客が登る必要のある層の総数はY +（N1 + N2-N3）層です。 N1> N2 + N3の場合、エレベータはi-1階でよりよく停止し、乗客が歩く階数が減少することがわかります（N1-N2-N3）
N1 + N2> N3の場合、エレベータはi + 1階で停止し、それ以外の場合は停止しやすくなります。エレベータをi階で停止することをお勧めします。
このルールに基づいて、1階から調べ、各乗客が登る必要のある階段の数を計算し始めました。次に、最適なフロアが見つかるまで、上記の戦略に従って調整します。合計時間計算量はO（N）に削減されます
package com.floor /*** * Elevator optimization method * * */ public class Floor { public static void main(String[] args) { getMinFloors(4, 1) betterFloors() } // Double-layer loop method, calculate how many stairs the passenger has to climb. . Time complexity is o(N^2) public static void getMinFloors(int nTargetFloor, int nMinFloor) { // The following are the number of people going to the elevator floor int[] persons = { 0, 2, 0, 1, 3, 5, 8, 4, 6, 0 } Int N = 9// How many layers are there in the elevator? for (int i = 1 i <= N i++) { int nFloor = 0 for (int j = 1 j < i j++) { nFloor += persons[j] * (i - j)// Calculate the number of floors to climb down } for (int j = i + 1 j nFloor) { nMinFloor = nFloor nTargetFloor = i } System.out.println('If you stop at the '+i+' layer you need to climb' + nFloor + ': Elevator') } } // Better method public static void betterFloors() { // The following are the number of people going to the elevator floor int[] persons = { 0, 2, 0, 1, 3, 5, 8, 4, 6, 0 } Int N = 9// How many layers are there in the elevator? int nTargetFloor = 1 int nMinFloor = 0 int N1 = 0, N2 = persons[1], N3 = 0 for (int i = 2 i <= N i++) { N3 += persons[i] nMinFloor += persons[i] * (i - 1)//First calculate the sum of the floors that should be climbed } for (int i = 2 i <= N i++) { if (N1 + N2 < N3) { nTargetFloor = i nMinFloor += (N1 + N2 - N3) N1 += N2 N2 = persons[i] N3 -= persons[i] } else { break } } System.out.println('Optimization method result: stop at the first' + nTargetFloor + 'layer to climb:' + nMinFloor + 'time') } }