プログラミングの美しさ:第1章1.5機械の故障を迅速に探し出す
2326 ワード
/*マシン障害を迅速に特定:検索エンジンのサービス品質を保証するために、各データに複数のバックアップがあることを保証する必要があります.1つのマシンにIDと表記されたレコードが1つしか保存されていないと仮定し(IDは10億未満の整数と仮定します)、各データに2つのバックアップが保存されていると仮定すると、2つのマシンに同じデータが格納されます.1ある時点で、1つのデータファイルIDのリストが得られると、このテーブルに1回しか現れないIDを素早く見つけることができるか.2マシンが1台しかハングアップしていないことを知っていたら(つまりバックアップが1つしかないということです)もし2台の機械が4級あったら(同じデータの2つの世代が同時に失われないと仮定します)?3紛失した2台のマシンIDが同じなら?
分析:この問題は変換することができます:多くのIDがあって、その中でただ1つのIDの出現回数は2より小さくて、その他の正常なIDの出現回数はすべて2に等しくて、どのようにこの回数が1のIDを探し当てます.このように剣の指の上のに転化します:すべての元素はすべて異なって、最終的に残った数はその数です
第2問はこの群数のうち2つの数が1回ずつ出現し、残りは0回出現するので剣指上の問題でもあり、すべての異または数字xを得る必要があり、それからxのビット表現の中で最も右側の1を取得し、そのビット表現の中のn番目のビットが1であるかどうかによって、配列を2つの部分に分け、各部分の中でそれぞれすべての異または1回であればよい.制限:2台の故障機器IDが異なる場合のみ解決できます.IDが同じでは解決できません
第三問:全IDの合計(不変量)を予め計算して保存し、現在の残りのIDを順番に列挙し、それらを合計し、総額-残り値=デッドラインのマシンID値を用いる.総和は先に計算できるので,アルゴリズムの時間的複雑度はO(N),空間的複雑度はO(1)である.
2つのIDが異なる場合:合計-残余および=x+y 2つのIDが同じ場合:この場合、x=(合計-残余および)/2
このとき,二元一次方程式群を構築して行うことができる,例えば,総積/余剰積=x*y(あるいはx*x+y*y=bを求める)連立解方程式{x+y=a{x*y=bこの方法の欠陥は,元のn個の数を事前に知る必要があり,問題が失われた数だけを与えると,お父さんになる
サンプル入力:8 2 4 3 6 3 2 5 5 2 4 3 6 3 3 2 5 4 6サンプル出力:4 6*/
分析:この問題は変換することができます:多くのIDがあって、その中でただ1つのIDの出現回数は2より小さくて、その他の正常なIDの出現回数はすべて2に等しくて、どのようにこの回数が1のIDを探し当てます.このように剣の指の上のに転化します:すべての元素はすべて異なって、最終的に残った数はその数です
第2問はこの群数のうち2つの数が1回ずつ出現し、残りは0回出現するので剣指上の問題でもあり、すべての異または数字xを得る必要があり、それからxのビット表現の中で最も右側の1を取得し、そのビット表現の中のn番目のビットが1であるかどうかによって、配列を2つの部分に分け、各部分の中でそれぞれすべての異または1回であればよい.制限:2台の故障機器IDが異なる場合のみ解決できます.IDが同じでは解決できません
第三問:全IDの合計(不変量)を予め計算して保存し、現在の残りのIDを順番に列挙し、それらを合計し、総額-残り値=デッドラインのマシンID値を用いる.総和は先に計算できるので,アルゴリズムの時間的複雑度はO(N),空間的複雑度はO(1)である.
2つのIDが異なる場合:合計-残余および=x+y 2つのIDが同じ場合:この場合、x=(合計-残余および)/2
このとき,二元一次方程式群を構築して行うことができる,例えば,総積/余剰積=x*y(あるいはx*x+y*y=bを求める)連立解方程式{x+y=a{x*y=bこの方法の欠陥は,元のn個の数を事前に知る必要があり,問題が失われた数だけを与えると,お父さんになる
サンプル入力:8 2 4 3 6 3 2 5 5 2 4 3 6 3 3 2 5 4 6サンプル出力:4 6*/
#include <stdio.h>
#include <math.h>
const int MAXSIZE = 10000;
void process()
{
int n;
while(EOF != scanf("%d",&n))
{
if(n < 0)
{
break;
}
int iRemainArr[MAXSIZE];
long long lRemainSum = 0,lRemainMul = 1,lIntactSum = 0,lIntactMul = 1;
for(int i = 0 ; i < n ; i++)
{
scanf("%d",&iRemainArr[i]);
lRemainSum += iRemainArr[i];
lRemainMul *= iRemainArr[i];
}
int iIntactArr[MAXSIZE];
for(int j = 0 ; j < n + 2 ; j++)
{
scanf("%d",&iIntactArr[j]);
lIntactSum += iIntactArr[j];
lIntactMul *= iIntactArr[j];
}
long long lSum = lIntactSum - lRemainSum;
long long lMul = lIntactMul/lRemainMul;
long long lSqrt = (long long)sqrt(double(lSum*lSum - 4*lMul) + 0.5);
long long lX = (long long)((lSum - lSqrt)/2);
long long lY = (long long)((lSum + lSqrt)/2);
printf("%lld %lld
",lX,lY);
}
}
int main(int argc,char* argv[])
{
process();
getchar();
return 0;
}