Data Structures and Algorithm Analysis in c++第一章ノートと一部の練習問題
注:入力の問題はおっくうで、AはAのX次方logA(B)は底数Aを表して、真数はBプラスマイナス乗除などの+-*/=指数exponent A*A=A A/A=A A=A+A=2*A!=A<2*X>2+2=2*2=2<1+X>対数Logarithmsはコンピュータ科学において、すべての対数の底数はデフォルトで2定義されている:A=Bがある場合、logA(B)=Xのみであり、XをAをベースBとする対数1:logA(B)=logC(B)/logC(A)と呼ぶ. A,B,C > 0, A!=1証明:Z=logA(B)を仮定する;=>A=B=>式3 X=logC(A);=>C=A=>式1 Y=logC(B);=>C=B=>式2式1,2を3得:=>C=C=>X*Z=Y=>Y/X=Zに代入する.得証2:log(AB)=log(A)+log(B);A,B>0証明:Z=log(AB)を仮定する;=>2=AB=>式3 X=log(A);=>2=A=>式1 Y=log(B);=>2=B=>式2式1,2を3得:=>2=2*2=>Z=Y+Xに代入する.得証3:log(A/B)=log(A)-log(B);A,B>0証明:Z=log(A/B)を仮定する;=>2=A/B=>式3 X=log(A);=>2=A=>式1 Y=log(B);=>2=B=>式2式1,2を3得:=>2=2/2=>Z=X-Yに代入する.得証4:log(A)=B*log(A);A,B>0証明:Z=log(A)を仮定する;=>2=A=>式3 X=log(A);=>2=A=>式1式を3得:=>2=2=>Z=X*Bに代入する.得証5:log(X)0証明:0log(X)+log(2)=log(2 X)>log(X+1)級数series常用求和式:i[0,n],2の和:2-1設定:Sn=1+2+2<2>+...+2等式両端に2:2*Sn=2+2<2>+2<3>+…+を乗じる2二式相減Sn=2-1 i[0,n],Aの和:(A-1)/(A-1)設定:Sn=1+A+A<2>+…+A式両端にA*Sn=A+A<2>+A<3>+...+を乗じるA両式相減(A−1)Sn＝A−1 Sn＝(A−1)／(A−1)同理0＜A＜1(1−A)Sn<＝1 Sn<＝1 Sn<＝1／(1−A)i［1,n］,i／(2)の和:Sn<＝2とする:Sn＝1／2＋2／4＋3／8＋…＋n/(2)式両端にA:2*Sn=1+2/2+3/4+3/8+...+を乗じるn/(2)二式相減Sn=1+1/2+1/4+…Sn<=2 i[1,n],i<2>の和:n(n+1)(2 n+1)/6はn<3>/3 i[1,n],iの和:n/(k+1)i[1,n],1/iの和:loge(n)モード演算modにほぼ等しいA-BがNで除算されると、AをNまたはBで除算し、残数はいずれも同じであり、AB同余と呼ばれ、A≡B(mod N)と表記すると、A+CとB+Cが同余となり、A*CとB*CはNに対して同じ素数(prime number、1と自身でのみ割り切れる):1 A≡0(mod N)またはB≡0(mod N)の場合のみAB≡0(mod N)2.Ax≡1(mod N)は、0≡A(mod N)は、0の和:n(n+1)(n+1)(n+1)(n+1)/6 i=nに対して、n<2>の和をn(n+1)(n+1)(n+1)/6 i=n+1に対して、(n+1)<2>の和を、n(n+1)(n n+1)(n+1)(n+1)(n+1)<2>(n+1)*[n(2 n+1)/6+(n+1)*[(n n n<2>+7 n+6)/6](n+1)*[(n+2 n+3)(n+2)/6]n+1)(n+1)(n+1)(n+1)(n+1)(n 1)+1)/6得証再帰recursive 1.再帰を必要としないで解くことができる基本的な状況(base case)2が存在しなければならない.再帰的に解く必要があるすべての状況は、最終的には(Making progress)の基本的な状況に帰す必要がある.design ruleは、すべての再帰が正しいと仮定する.Compound interest ruleは、同じ問題の同じインスタンスに対して、再帰的にc++テクニックを繰り返してはいけません.クラスのコンストラクション関数でパラメータがクラスタイプの場合、初期化リスト(initialization list)を使用すると、付与文(assignment statement)よりも優れ、初期化リストを使用してコンストラクション関数を直接呼び出し、付与は一般的に一時オブジェクトを構築します.次に、練習1.5:Write a recursive function that returns the number of 1 in the binary representation ofN.Use the fact that this is equal to the number of 1 in the representation ofN/2, plus 1, if N is odd.
std::size_t last_bit(std::size_t n){ if (n == 0) return 0; return (n & 1u) + last_bit(n >> 1u); //equal to n/2 }
練習1.8 1>i[0,n],1/(4)の和は式によって約4/3 2>i[0,n],i/(4)の和Sn=1/4+2/16+3/64+に等しい. 4*Sn = 1 + 2/4 + 3/16 + ... 3*Sn=1+1/4+1/16=4/3 Sn=4/9 3>i[0,n],i/(4)和Sn=1/4+4/16+9/64+ 4*Sn = 1 + 4/4 + 9/16 + ... 3*Sn = 1 + 3/4 + 5/16 + ... =5*i/(4)和=20/27練習1.9 i[1,n/2]、1/i和ln(n)−ln(n/2−1)=ln(n)−ln(n/2)−ln(n/2)=ln 2
練習1.10 2<100>(mod 5)=1 2<4>(mod 5)=1 2<100>=(2<4>)<25>=1<25>=1
練習は1.11できません...
練習1.12 a>証明i[1,n]2 i−1の和はn<2>2(n+1)−1+n<2>=n<2>+2 n+1=(n+1)<2>に等しい
b>証明i[1,n]i<3>の和がi[1,n]iの和の二乗(n+1)<3>+(1+n)<2>*n<2>/4=(n+1)<2>*(n/2+1)<2>=[(n+1)/2]<2>練習1.15
//==================================
//===================================
//===========================================
//==================================
std::size_t last_bit(std::size_t n){ if (n == 0) return 0; return (n & 1u) + last_bit(n >> 1u); //equal to n/2 }
練習1.8 1>i[0,n],1/(4)の和は式によって約4/3 2>i[0,n],i/(4)の和Sn=1/4+2/16+3/64+に等しい. 4*Sn = 1 + 2/4 + 3/16 + ... 3*Sn=1+1/4+1/16=4/3 Sn=4/9 3>i[0,n],i/(4)和Sn=1/4+4/16+9/64+ 4*Sn = 1 + 4/4 + 9/16 + ... 3*Sn = 1 + 3/4 + 5/16 + ... =5*i/(4)和=20/27練習1.9 i[1,n/2]、1/i和ln(n)−ln(n/2−1)=ln(n)−ln(n/2)−ln(n/2)=ln 2
練習1.10 2<100>(mod 5)=1 2<4>(mod 5)=1 2<100>=(2<4>)<25>=1<25>=1
練習は1.11できません...
練習1.12 a>証明i[1,n]2 i−1の和はn<2>2(n+1)−1+n<2>=n<2>+2 n+1=(n+1)<2>に等しい
b>証明i[1,n]i<3>の和がi[1,n]iの和の二乗(n+1)<3>+(1+n)<2>*n<2>/4=(n+1)<2>*(n/2+1)<2>=[(n+1)/2]<2>練習1.15
//==================================
#ifndef RECTANGLE_H
#define RECTANGLE_H
#include
class Rectangle{
public:
using sz = std::size_t;
friend std::ostream & print(std::ostream &, const Rectangle &);
Rectangle(sz w = 0, sz l = 0) : width(w), length(l){ }
sz get_length() const {
return length;
}
sz get_width() const {
return width;
}
private:
sz width;
sz length;
};
//show Rectangle's data members
std::ostream & print(std::ostream & os, const Rectangle & rc){
return os << rc.get_length() << " - " << rc.get_width();
}
#endif // RECTANGLE_H //===================================
#ifndef FINDMAX_H
#define FINDMAX_H
#include
template
const Object & find_max(const std::vector //===========================================
#ifndef COMPARING_H
#define COMPARING_H
//compare area
template
class comparing_area{
public:
bool operator()(const Object & rec1, const Object & rec2) const {
return rec1.get_width() * rec1.get_length() > rec2.get_width() * rec2.get_length();
};
};
//compare perimeter
template
class comparing_perimeter{
public:
bool operator()(const Object & rec1, const Object & rec2) const {
return rec1.get_width() + rec1.get_length() > rec2.get_width() + rec2.get_length();
};
};
#endif //COMPARING_H //==================================
#include
#include
#include "Rectangle.h"
#include "Findmax.h"
#include "Comparing.h"
#define RANDOM(x) (std::rand()%x)
int main(){
std::vector vr;
std::size_t i = 0;
std::srand(std::time(0));
//generate a array of Rectangle by rand()
while (i != 10){
vr.push_back(Rectangle(RANDOM(10) + 1, RANDOM(10) + 1));
//show Rectangle
print(std::cout, vr[i]) << std::endl;
++i;
}
std::cout << "******" << std::endl;
//show the max Rectangle on the basis of area
print(std::cout, find_max(vr, comparing_area< Rectangle>{}));
std::cout << "******" << std::endl;
//show the max Rectangle on the basis of perimeter
print(std::cout, find_max(vr, comparing_perimeter< Rectangle>{}));
return 1;
}