算法設(shè)計與分析課后總結(jié)-創(chuàng)新互聯(lián)

（1）

int Stery(int n)
{int S=0;
	for(int i=1;i<=n;i++)
		S+=i*i;
	return S;
}

完成功能：計算 ∑ i = 1 n i 2 \sum_{i=1}^n i^2 ∑i=1n?i2
基本語句：S+=i*i;
算法復雜度： O ( n ) O(n) O(n)
(2)

int Q(int n)
{if(n==1)
		return 1;
	else
		return Q(n-1)+2*n-1;
}

完成功能： ∑ i = 1 n ( 2 n ? 1 ) = n 2 \sum_{i=1}^n(2n-1)=n^2 ∑i=1n?(2n?1)=n2
基礎(chǔ)語句：2*n-1
時間復雜度： O ( n ) O(n) O(n)

(1)

for(i=1;i<=n;i++)
	if(2*i<=n)
		for(j=2*i;j<=n;j++)
			y+=i*j;

基礎(chǔ)語句：y+=i*j
執(zhí)行次數(shù)： ∑ i = 1 n / 2 ( n ? 2 i ) = n ( n ? 2 ) 4 \sum_{i=1}^{n/2}(n-2i)=\frac{n(n-2)}{4} ∑i=1n/2?(n?2i)=4n(n?2)?
時間復雜度： O ( n 2 ) O(n^2) O(n2)
(2)

m=0;
for(i=1;i<=n;i++)
	for(j=1;j<=2*i;j++)
		m+=1;

基礎(chǔ)語句：m+=1
執(zhí)行次數(shù)： ∑ i = 1 n 2 i = n ( n + 1 ) \sum_{i=1}^n2i=n(n+1) ∑i=1n?2i=n(n+1)
時間復雜度： O ( n 2 ) O(n^2) O(n2)

(1) T ( n ) = { 4 n = 1 3 T ( n ? 1 ) n > 1 T(n) = \begin{cases} 4 &n=1 \\ 3T(n-1) & n>1 \\ \end{cases} T(n)={43T(n?1)?n=1n>1?
解： T ( n ) = 3 T ( n ? 1 ) = . . . = 3 n ? 1 T ( 1 ) = 4 × 3 n ? 1 T(n)=3T(n-1)=...=3^{n-1}T(1)=4×3^{n-1} T(n)=3T(n?1)=...=3n?1T(1)=4×3n?1
(2) T ( n ) = { 1 n = 1 2 T ( n / 3 ) + n n > 1 T(n)= \begin{cases} 1 &n=1\\ 2T(n/3)+n &n>1\\ \end{cases} T(n)={12T(n/3)+n?n=1n>1?
解：令 n = 3 k n=3^k n=3k
T ( n ) = 2 T ( n / 3 ) + n = 2 ( 2 T ( n / 3 2 ) + n / 3 ) + n = . . . = 2 k ∑ i = 0 k ( 3 k / 2 i ) T(n)=2T(n/3)+n=2(2T(n/3^2)+n/3)+n=...=2^k\sum_{i=0}^k(3^k/2^i) T(n)=2T(n/3)+n=2(2T(n/32)+n/3)+n=...=2k∑i=0k?(3k/2i)

void dlt(int r*,int n,int x)
{int j=0;
	for(int i=0;iif(r[i]!=x)
		{	r[j]=r[i];
			j++;
		]
	}
}

算法思想：雙重循環(huán)找重復值，將重復元素設(shè)置為固定值flag，再用上一題的代碼刪除即可

void dlt2(int r*,int n)
{flag=-1;
	for(int i=0;iif(i==flag)continue;
		for(int j=i+1;j++)
		{	if(a[i]==a[j])
				a[j]=flag;
		}
	}
	dlt(r,flag);
}

算法思想：將A分為左邊和右邊，左邊的數(shù)大于0，右邊的數(shù)小于0即可

int divorce(int A*,int n)
{int i=0,j=n-1;
	while(iwhile(A[i]>=0&&i

int Max(int *A,int low,int hight)
{if(low>hight)
		return -1;
	else if(low==hight)return A[low];
	int mid=(low+hight)/2;
	return max(Max(A,low,mid),Max(A,mid+1,hight));
}

int find(int *A,int low,int height)
{if(low>hight)
		return -1;
	if(low==height)
	{if(A[low]==low) return low;
		else return -1;
	}
	int mid=(low+hight)/2;
	if(A[mid]=mid)
	{return mid;
	}
	else if(A[mid]>mid)
		return find(A,low,mid-1);
	else
	   return find(A,mid+1,height);
}

int part(int* r, int low, int hight)  
{int i = low, j = hight, pivot = r[low]; 
	while (i< j)
	{while (ipivot) j--;
		if (i< j)	swap(r[i++], r[j]);  
		while (i< j && r[i]<= pivot) 	i++;
		if (i< j)	swap(r[i], r[j--]);  
	}
	return i;  
}
void Quicksort(int* r, int low, int hight)
{int mid;
	if (low< hight)
	{mid = part(r, low, hight);  // 返回基準元素位置
		Quicksort(r, low, mid - 1); // 左區(qū)間遞歸快速排序
		Quicksort(r, mid+1, hight); // 右區(qū)間遞歸快速排序
	}
}

int mode(int A*,int n)
{Quicksort(A,0,n-1);
	int Max=0;
	for(int i=0;iint t=a[i];
		int num=0;
		while(i

int divfind(int *A,int low,int hight,int x)
{if(low>height)
		return false;
	mid=(low+height)/2;
	if(A[mid]==x)
		return mid;
	else if(A[mid]>x)
		return divfind(A,low,mid-1);
	else
		return divfind(A,mid+1,height);
}

#include#include#includeusing namespace std;


//查找最小邊函數(shù)  Search 
pairSearch(int **A,int N,int *flag,int **AF) {//查找最小邊

 int min=10e5,a=0,b=0;
 for(int i=0; ifor(int j=0; jif(!AF[i][j]&&flag[i]<2&&flag[j]<2&& A[i][j]//如果這條邊沒有走過，兩邊的城市沒有同時有兩個被走過的邊 
    a=i; 
    b=j;
    min=A[i][j];//依次比較 
   }
  }
 }
 flag[a]++;
 flag[b]++;
 AF[a][b]=1;
 return pair(a,b);
}



//TSP2
int TSP2(int **A,int N,int *flag,int **AF) {int tsp=0,i,j,k;
 for(k=0; k//選擇N次最短邊 
  paira=Search(A,N,flag,AF);
  tsp+=A[a.first][a.second];//每次加入最增的最短邊 
 }
 return tsp;
}




int main() 
 { 	//N初始化
	 int N=5; 
 	
	 	
 	//A初始化(城市之間的距離)
 	int **A=(int **)malloc(N*sizeof(int));
	cout<<"輸入5個城市之間的距離(0表示城市間不通):"<A[i]=(int*)malloc(N*sizeof(int));
		for(int j=0;j	cin>>A[i][j];
		}
	}		 
	
		
	//AF初始化，記錄邊是否走過 
	int **AF=(int **)malloc(N*sizeof(int));//記是否邊走過，初始值設(shè)為0，走過設(shè)為1
	for(int i=0;iAF[i]=(int*)malloc(N*sizeof(int));
		for(int j=0;j	AF[i][j]=0;
		}
	}
 	  
 	  
 	//flag初始化,記錄城市是否走過 
	int *flag=(int *)malloc(N*sizeof(int));//標記是否城市走過，初始值設(shè)為0，走進去又走出來成為2 
    for(int i=0;iflag[i]=0;
	}
	   
	  	  
    cout<<"最短路徑長度：";
	cout<