配列の等分点を探します&&指数の高速べき乗
2079 ワード
1.O(n)の時間内に3つの点を見つけることを要求する配列を与え、この3つの点によって決定された4つの配列の要素と等しい、すなわち4等分点を探す.
二等分点を探したい場合は、要素の前後の和が等しくなるまで、シミュレーションポインタで各要素を順次指すだけです.ここでは4等分点の原理が等しいことを探し,3つのシミュレーションポインタで3つの位置を指し,この3つのポインタの位置を比較し調整することによって適切な区分を見つけた.具体的なコード:
循環体にはいくつかの判断があります.例えば、第1段と第2段の比較では、第1段が小さいと1番のポインタを後ろに移動させ、第1段が増加し、第2段が減少します.後の比較は処理と同じです.
戻り値は3つの位置が格納されている配列で、見つからない場合はnullを返します
2.指数の高速べき乗:
doubleのint乗を計算します.この指数intは非常に大きく,直接計算できない.
考え方はこうです.0.7の9乗を計算する場合は、(0.7)^2^2*0.7と見なすことができます.これで4回の乗算しか行われません.つまり、Int型の指数は、9が1001、=8+1のようなバイナリ数と見なすことができ、8回と1回だけを計算する必要があります.コード:
二等分点を探したい場合は、要素の前後の和が等しくなるまで、シミュレーションポインタで各要素を順次指すだけです.ここでは4等分点の原理が等しいことを探し,3つのシミュレーションポインタで3つの位置を指し,この3つのポインタの位置を比較し調整することによって適切な区分を見つけた.具体的なコード:
public int[] four(int[] a){
int length=a.length-1;
int firstPosition=1;
int secondPosition=3;
int thirdPosition=5;
int sum1,sum2,sum3,sum4;
do{
sum1=sum2=sum3=sum4=0;//
for(int i=0;isum2){
if(secondPositionsum3){
if(thirdPositionsum4){
thirdPosition=length;
}
}while(!(sum1==sum2&&sum2==sum3&&sum3==sum4)&&secondPosition!=length&&thirdPosition!=length);
int[] result=new int[3];
if (secondPosition==length||thirdPosition==length) {
result=null;
} else {
result[0]=firstPosition+1;
result[1]=secondPosition+1;
result[2]=thirdPosition+1;
}
return result;
}
ここでは、アナログポインタが指す位置を4つのIntで表し、4つのIntは4つのセグメントの和を表します.本体はdo whileサイクルで、ジャンプ条件は4段と同じまたは2番の3番のポインタが末尾を指す(データを代入してテストすることができ、等分点が見つからない場合は2番または3番のポインタが末尾を指す).循環体にはいくつかの判断があります.例えば、第1段と第2段の比較では、第1段が小さいと1番のポインタを後ろに移動させ、第1段が増加し、第2段が減少します.後の比較は処理と同じです.
戻り値は3つの位置が格納されている配列で、見つからない場合はnullを返します
2.指数の高速べき乗:
doubleのint乗を計算します.この指数intは非常に大きく,直接計算できない.
考え方はこうです.0.7の9乗を計算する場合は、(0.7)^2^2*0.7と見なすことができます.これで4回の乗算しか行われません.つまり、Int型の指数は、9が1001、=8+1のようなバイナリ数と見なすことができ、8回と1回だけを計算する必要があります.コード:
public double multify(double n,int k){//
double result=1.0d;
double temp=n;
while(k>0){
if (k%2==1){// , 1,
result=result*temp;
}
temp=temp*temp;
k=k>>1;
}
return result;
}
は、kの最低ビットが1であるか否かを判断するたびに、計算を行い、kが1ビット右にシフトするたびに、中間変数tempが二乗する.