1．Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and
another integer x, determines whether or not there exist two elements in S whose sum is exactly x. (Implement exercise 2.3-7.)
#include<stdio.h>
#include<stdlib.h>
void merge(int arr[],int low,int mid,int high){
int i,k;
int *tmp=(int*)malloc((high-low+1)*sizeof(int));
int left_low=low;
int left_high=mid;
int right_low=mid+1;
int right_high=high;
for(k=0;left_low<=left_high&&right_low<=right_high;k++)
{
if(arr[left_low]<=arr[right_low]){
tmp[k]=arr[left_low++];
}
else{
tmp[k]=arr[right_low++];
}
}
if(left_low<=left_high){
for(i=left_low;i<=left_high;i++){
tmp[k++]=arr[i];
}
}
if(right_low<=right_high){
for(i=right_low;i<=right_high;i++)
tmp[k++]=arr[i];
}
for(i=0;i<high-low+1;i++)
arr[low+i]=tmp[i];
}
void merge_sort(int a[],int p,int r){
int q;
if(p<r){
q=(p+r)/2;
merge_sort(a,p,q);
merge_sort(a,q+1,r);
merge(a,p,q,r);
}
}
int main(){
int a[8]={3,5,8,6,4,1,1};
int i,j;
int x=10;
merge_sort(a,0,6);
printf("after Merging-Sort:\n");
for(i=0;i<7;i++){
printf("%d",a[i]);
}
printf("\n");
i=0;j=6;
do{
if(a[i]+a[j]==x){
printf("exist");
break;
}
if(a[i]+a[j]>x)
j--;
if(a[i]+a[j]<x)
i++;
}while(i<=j);
if(i>j)
printf("not exist");
system("pause");
return 0;
}
標簽：
c語言
算法
排序
上傳時間：
2017-04-01
上傳用戶：糖兒水嘻嘻
function [alpha,N,U]=youxianchafen2(r1,r2,up,under,num,deta)
%[alpha,N,U]=youxianchafen2(a,r1,r2,up,under,num,deta)
%該函數用有限差分法求解有兩種介質的正方形區域的二維拉普拉斯方程的數值解
%函數返回迭代因子、迭代次數以及迭代完成后所求區域內網格節點處的值
%a為正方形求解區域的邊長
%r1,r2分別表示兩種介質的電導率
%up,under分別為上下邊界值
%num表示將區域每邊的網格剖分個數
%deta為迭代過程中所允許的相對誤差限
n=num+1; %每邊節點數
U(n,n)=0; %節點處數值矩陣
N=0; %迭代次數初值
alpha=2/(1+sin(pi/num));%超松弛迭代因子
k=r1/r2; %兩介質電導率之比
U(1,1:n)=up; %求解區域上邊界第一類邊界條件
U(n,1:n)=under; %求解區域下邊界第一類邊界條件
U(2:num,1)=0;U(2:num,n)=0;
for i=2:num
U(i,2:num)=up-(up-under)/num*(i-1);%采用線性賦值對上下邊界之間的節點賦迭代初值
end
G=1;
while G>0 %迭代條件：不滿足相對誤差限要求的節點數目G不為零
Un=U; %完成第n次迭代后所有節點處的值
G=0; %每完成一次迭代將不滿足相對誤差限要求的節點數目歸零
for j=1:n
for i=2:num
U1=U(i,j); %第n次迭代時網格節點處的值
if j==1 %第n+1次迭代左邊界第二類邊界條件
U(i,j)=1/4*(2*U(i,j+1)+U(i-1,j)+U(i+1,j));
end
if (j>1)&&(j U2=1/4*(U(i,j+1)+ U(i-1,j)+ U(i,j-1)+ U(i+1,j));
U(i,j)=U1+alpha*(U2-U1); %引入超松弛迭代因子后的網格節點處的值
end
if i==n+1-j %第n+1次迭代兩介質分界面（與網格對角線重合）第二類邊界條件
U(i,j)=1/4*(2/(1+k)*(U(i,j+1)+U(i+1,j))+2*k/(1+k)*(U(i-1,j)+U(i,j-1)));
end
if j==n %第n+1次迭代右邊界第二類邊界條件
U(i,n)=1/4*(2*U(i,j-1)+U(i-1,j)+U(i+1,j));
end
end
end
N=N+1 %顯示迭代次數
Un1=U; %完成第n+1次迭代后所有節點處的值
err=abs((Un1-Un)./Un1);%第n+1次迭代與第n次迭代所有節點值的相對誤差
err(1,1:n)=0; %上邊界節點相對誤差置零
err(n,1:n)=0; %下邊界節點相對誤差置零
G=sum(sum(err>deta))%顯示每次迭代后不滿足相對誤差限要求的節點數目G
end
標簽：
有限差分
上傳時間：
2018-07-13
上傳用戶：Kemin
