第一章 Procedure F(A, n) ←n; count0;m←0; while j20 do if a[]=1 then count+count 1 else if count mod 2#o then m←m+1; endif count←-0; endif 1; repeat if m>0 then return(false) else return(true) endif Endf
第一章 Procedure F(A,n) i←n; count←0;m←0; while i≥0 do if A[i] =1 then count←count + 1; else if count mod 2 ≠ 0 then m←m+1; endif count←0; endif i←i-1; repeat if m＞0 then return(false) else return(true) endif End F
int judge(int al l, int n) int I, flag =0 for(=1;-sn;i++){ Whe(A[]==1&&≤n) flag =(flag +A[i++]%2 if(flag) return(false) return(true);∥如果没有任何连续为1的序列?
int judge(int A[ ],int n) { int I, flag = 0; for(i=1;i≤n;i++) { while(A[i]== 1 && i≤n) flag =(flag + A[i++])%2; if(flag) return(false); } return(true); //如果没有任何连续为1的序列？ }
int check(int al ], int n int i=0, k=0, flag =1 while(isnt k=0 Whle(A[==0)计++;∥&i<n Whle(A[==1)k++;∥/i++&&i<n if(k/ i flag=0 break return(fag);∥如果没有任何连续为1的序列?
int check(int a[ ],int n) { int i=0, k=0, flag = 1; while(i＜n) { k=0; while(A[i]== 0) i++; //&&i<n while(A[i]== 1) k++; // i++ && i<n if(k%2) { flag = 0; break; } return(flag); //如果没有任何连续为1的序列？ }
第二章 2.化简递推关系式 ∴g(n)=0(1) ∴可令g(n)=c1(或简单令g(n)=1) 同理 f(n)=0(n) ∴可令f(n)=c2n(或简单令f(n)=n,或f(n)=c2n+b), 可设c1=C2=C 化简 T(n)=2T(n/2)+f(n) 2T(n/2)+cn =4T(n/4)+2(cn/2)+cn=4T(n/4)+2cn 2kT(n/2k)+kcn 若n=2,则k=logn .T(n)=cn+cnlogn=o(nlogn) 当n∈[2k,2k+1),T(n)=cn+ cologne=e( nlogn)
第二章 2. 化简递推关系式 ∵g(n)=O(1) ∴可令 g(n)=c1(或简单令g(n)=1) 同理， ∵f(n)=O(n) ∴可令 f(n)=c2n(或简单令f(n)=n，或f(n)=c2n＋b), 可设c1=c2=c 化简 T(n)=2T(n/2)+f(n) =2T(n/2)+cn =4T(n/4)+2(cn/2)+cn=4T(n/4)+2cn =… =2kT(n/2k)+kcn 若n=2k ,则k=logn ∴T(n)=cn+cnlogn=O(nlogn) 当n∈[2k,2k+1), T(n)=cn+cnlogn=Θ(nlogn)
g(n)=0(1 可令g(n)=c1(或简单令g(n)=1) 同理 f(n)=0(1) 可令f(n)=c2(或简单令f(n)=1), 可设C1=C2=C 化简 T(n)=2T(n/2)+f(n) =2T(n/2)+c =4T(n/4)+2c+c =8T(n/8)+22c+2c+c=… 2T(n/2k)+(1+2+22+…+2k-1) C-cn+(2k- C . cn-c=o(n)
∵g(n)=O(1) ∴可令 g(n)=c1(或简单令g(n)=1) 同理， ∵f(n)=O(1) ∴可令 f(n)=c2(或简单令f(n)=1), 可设c1=c2=c 化简 T(n)=2T(n/2)+f(n) =2T(n/2)+c =4T(n/4)+2c+c =8T(n/8)+22c+2c+c=… =2kT(n/2k)+(1+2+22+…+2k-1)c=cn+(2k-1)c =2cn-c=O(n)