//1欧几里德算法
#include<stdio.h>
int main()
{ int k,m,i,n,r;
scanf("%d%d",&n,&m);
if(n>m) //保证m>n
{ k=n;
n=m;
n=k;}
if(n==0)
printf("%d",m);
for(i=n;i>0;i--)
{if(m%n==0)
{ printf("%d",n);
break;}
else
{ r=m%n;
m=n;
n=r;
}
}
}
//2大数加法
#include <stdio.h>
#include <string.h>
#define MAXLEN 1000
char a1[MAXLEN];
char a2[MAXLEN];
static int v1[MAXLEN];
static int v2[MAXLEN];
static int v3[MAXLEN];
int i,n,L,z;
void main(void)
{ gets(a1); //输入数a1
gets(a2); //输入数a2
L=strlen(a1);
for (i=0;i<L;i++) v1[i]=a1[L-1-i]-'0'; //反序a1数组
L=strlen(a2);
for (i=0;i<L;i++) v2[i]=a2[L-1-i]-'0'; //反序a2数组
for (i=0;i<MAXLEN;i++) v3[i]=v1[i]+v2[i]; //模拟十进制加法
for (i=0;i<MAXLEN;i++)
{
if (v3[i]>=10)
{
v3[i+1]+=v3[i]/10;
v3[i]=v3[i]%10;
}
}
z=0;
for (i=MAXLEN-1;i>=0;i--)
{
if (z==0)
{
if (v3[i]!=0)
{
printf("%d",v3[i]);
z=1;
}
}
else
{
printf("%d",v3[i]);
}
}
if (z==0)
printf("0");
printf("\n");
}
//3两人分财宝
#include<math.h>
#include<stdio.h>
#define MANX 1000
int main()
{ int y,z,s,t,i,j,m=0,n,sum=0;
int a[MANX];
scanf("%d ",&n);//输入财富的数量
if(n>10)
printf("error\n");
else
{ for(i=0;i<n;i++) //输入各财富的价值量
scanf("%d",&a[i]);
for(i=0;i<n;i++) //所有财富的总价值
sum=sum+a[i];
for(i=0;i<=n-2;i++) //冒泡排序，财富价值量数组从小到大排序
{ for(j=0;j<=n-2-i;j++)
if(a[j]>a[j+1])
{ t=a[j+1];
a[j+1]=a[j];
a[j]=t;}}
i=0;//转化为背包问题，尽可能放进总价值的一半
while(m<=(sum/2))
m=a[i++]+m;
if(m==sum)
m=m-a[i-1];
y=sum-2*m; //求他们的价值量之差的绝对值
z=abs(y);
printf("%d\n",z);//输出结果
}
}//4天平问题
#include<stdio.h>
#define MANX 1000
int main()
{ int a,b,c,d,e,i,j,k,m,n,total=0;
scanf("%d %d %d %d %d",&a,&b,&c,&d,&e);
if(a>=0&&a<=10&&b>=0&&b<=10&&c>=0&&c<=10&&d>=0&&d<=10&&e>=0&&e<=10)
{ for(i=0;i<=a;i++)
for(j=0;j<=b;j++)
for(k=0;k<=c;k++)
for(m=0;m<=d;m++)
for(n=0;n<=e;n++)
total++;
printf("%d\n",total);}
else
printf("error\n");
}
//5蛮力法求最近对问题
#include<stdio.h>
#include<math.h>
#define MAXN 60
main()
{ int n,i,j,d,x[MAXN],y[MAXN],min=99999;
float k;
scanf("%d",&n);
if(n<=1)
printf("error\n");
else if(n>50)
printf("error\n");
else
{
for(i=0;i<n;i++)
scanf("%d %d",&x[i],&y[i]);
for(i=0;i<n-1;i++)
for(j=i+1;j<=n-1;j++)
{ d=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
if(d<min)
min=d; }
k=sqrt(min);
printf("%.2f\n",k);
}
}
//6分治法求最近对问题
#include <stdio.h>
#include <math.h>
#define MAX 10
struct point{
int a;
int b;};
struct point Z[MAX+1];
void selection_sorta(struct point pt[],int n)
{ struct point t;
int i,j,k;
//int t;
for(i=1;i<n;i++)
{
k=i;
for(j=i+1;j<n+1;j++)
if(pt[k].a>pt[j].a)k=j;
if(k==j)
{ t.a=pt[i].a;
t.b=pt[i].b;
pt[i].a=pt[k].a;
pt[i].b=pt[k].b;
pt[k].a=t.a;
pt[k].b=t.b;
}
}
}
double dist(struct point u,struct point v)
{
double dx=u.a-v.a;
double dy=u.b-v.b;
return sqrt(dx*dx+dy*dy);
}
double closestpair(struct point X[],int low,int high)
{
double d,C;
double d1,d2,d3;
double dl,dr;
double best,best2;
int i,j,k;
int mid;
int x0;
best=0;
if((high-low)==1)
return dist(X[low],X[high]);
if((high-low)==2)
{ d1=dist(X[low],X[low+1]);
d2=dist(X[low+1],X[high]);
d3=dist(X[low],X[high]);
d=((d1<=d2 && d1<=d3)?d1:(d2<=d3?d2:d3));
return d;
}
else
{mid=(low+high)/2;
x0=X[mid].a;
dl=closestpair(X,low,mid);
dr=closestpair(X,mid+1,high);
best=(dl<=dr ? dl : dr);
k=1;
for(i=1;i<=high;i++)
if(abs(X[i].a-x0)<=best)
Z[k++]=X[i];
best2=2*best;
for(i=1;i<=k-1;i++)
{ for(j=i+1;j<((i+7)<=k ? (i+7) : k);j++)
if(dist(Z[i],Z[j])<best2)best2=dist(Z[i],Z[j]);
}
best=(best<=best2 ? best : best2);
return best;
}
}
int main()
{ int i;
int tempa,tempb;
double best;
struct point X[MAX+1];
printf("Input points:\n");
for(i=1;i<MAX+1;i++)
{ scanf("%d,%d",&tempa,&tempb);
X[i].a=tempa;
X[i].b=tempb;
}
selection_sorta(X,MAX);
best=closestpair(X,1,MAX);
printf("\n");
printf("%lf\n",best);
return 0;
}
//7折半查找
#include<stdio.h>
#define MAXN 100000
main()
{ int t,k,n,i,j,low=0,high,mid,a[MAXN];
scanf("%d",&n);
if(n>5000)
printf("error");
else
{ high=n-1;
for(i=0;i<n;i++)
scanf("%d",&a[i]);
scanf("%d",&k);
for(i=0;i<=n-2;i++) //防止是无序表，将其进行冒泡排序变成有序表
{ for(j=0;j<=n-2-i;j++)
if(a[j]>a[j+1])
{ t=a[j+1];
a[j+1]=a[j];
a[j]=t;}}
if(a[low]==k)
printf("%d\n",low+1);
else if(a[high]==k)
printf("%d\n",high+1);
else
while(high>=low)
{ mid=low+((high-low)/2);
if(a[mid]==k)
{ printf("%d\n",mid+1);
break;}
if(a[mid]>k)
high=mid-1;
else
low=mid+1;
if(low>high)
printf("查找失败"); }
}
}
//8最大字段和
#include <stdio.h>
#define N 10000
int MaxSumDP(int *a, int n);
int a[N];
int b[N];
int main()
{ int i,x;
scanf("%d",&x);
if(x>5000)
printf("error");
else
{
for(i=0;i<x;i++)
scanf("%d",&a[i]);
printf("%d\n", MaxSumDP(a, x));
return 0;
}}
int MaxSumDP(int *a, int x) //动态规划法
{
int i,maxSum=0;
if(a[0]>0)
maxSum=b[0]=a[0];
for(i=1;i<x;++i)
{
b[i]=(b[i-1]+a[i]>0)?(b[i-1]+a[i]):0;
if(maxSum<b[i])
maxSum=b[i];
}
return maxSum;
}
//9最长递增子序列
#include<stdio.h>
int main()
{ int i,j,k,n,a[100],b[100],c[100],max;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
b[0]=1;
c[0]=a[0];
k=1;
for(i=1;i<n;i++)
{ b[i]=1;
for(j=0;j<i;j++)
if(a[i]>a[j]&&b[j]+1>b[i])
{ b[i]=b[i]+1;
}
}
for(max=i=0;i<n;i++)
if(b[i]>max)
max=b[i];
printf("%d\n",max);
return 0;
}
//10Prim
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
#define MAXCOST 0x7fffffff
int graph[MAX][MAX];
int Prim(int graph[][MAX], int n)
{
int lowcost[MAX];
int mst[MAX];
int i, j, min, minid, sum = 0;
for (i = 2; i <= n; i++)
{ lowcost[i] = graph[1][i];
mst[i] = 1;
}
mst[1] = 0;
for (i = 2; i <= n; i++)
{
min = MAXCOST;
minid = 0;
for (j = 2; j <= n; j++)
{
if (lowcost[j] < min && lowcost[j] != 0)
{
min = lowcost[j];
minid = j;
}
}
printf("%c - %c : %d\n", mst[minid] + 'A' - 1, minid + 'A' - 1, min);
sum += min;
lowcost[minid] = 0;
for (j = 2; j <= n; j++)
{
if (graph[minid][j] < lowcost[j])
{
lowcost[j] = graph[minid][j];
mst[j] = minid;
}
}
}
return sum;
}
int main()
{
int i, j, k, m, n;
int x, y, cost;
char chx, chy;
scanf("%d%d", &m, &n);
getchar();
for (i = 1; i <= m; i++)
{
for (j = 1; j <= m; j++)
{
graph[i][j] = MAXCOST;
}
}
for (k = 0; k < n; k++)
{
scanf("%c %c %d", &chx, &chy, &cost);
getchar();
i = chx - 'A' + 1;
j = chy - 'A' + 1;
graph[i][j] = cost;
graph[j][i] = cost;
}
cost = Prim(graph, m);
printf("Total:%d\n", cost);
return 0;
}
//kruskal
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
typedef struct
{
int x, y;
int w;
}edge;
edge e[MAX];
int rank[MAX];
int father[MAX];
int sum;
int cmp(const void *a, const void *b)
{
if ((*(edge *)a).w == (*(edge *)b).w)
{
return (*(edge *)a).x - (*(edge *)b).x;
}
return (*(edge *)a).w - (*(edge *)b).w;
}
void Make_Set(int x)
{
father[x] = x;
rank[x] = 0;
}
int Find_Set(int x)
{
if (x != father[x])
{
father[x] = Find_Set(father[x]);
}
return father[x];
}
void Union(int x, int y, int w)
{
if (x == y) return;
if (rank[x] > rank[y])
{
father[y] = x;
}
else
{
if (rank[x] == rank[y])
{
rank[y]++;
}
father[x] = y;
}
sum += w;
}
int main()
{
int i, n;
int x, y;
char chx, chy;
scanf("%d", &n);
getchar();
for (i = 0; i < n; i++)
{
scanf("%c %c %d", &chx, &chy, &e[i].w);
getchar();
e[i].x = chx - 'A';
e[i].y = chy - 'A';
Make_Set(i);
}
qsort(e, n, sizeof(edge), cmp);
sum = 0;
for (i = 0; i < n; i++)
{
x = Find_Set(e[i].x);
y = Find_Set(e[i].y);
if (x != y)
{
printf("%c - %c : %d\n", e[i].x + 'A', e[i].y + 'A', e[i].w);
Union(x, y, e[i].w);
}
}
printf("Total:%d\n", sum);
return 0;
}
//12素数环
#include <stdio.h>
#include <math.h>
int primeRing(int ring[], int b[], int n,int LEN);
int isPrime(int n);
int main()
{ int LEN,i,ring[10000]={0},b[10000]={0};
scanf("%d",&LEN);
if(LEN<4)
printf("error\n");
else if(LEN>20)
printf("error\n");
else
{
ring[0] = 1;
b[0] = 1;
if( primeRing(ring, b, 1,LEN) )
{ for(i=0; i<LEN; i++)
printf("%d ", ring[i]);
printf("\n");
}
else
printf("NO\n");
return 0;
}}
int primeRing(int ring[], int b[], int n,int LEN)
{ int i;
if( n==LEN )
return isPrime(ring[n-1]+ring[0]);
for(i=1; i<LEN; i++)
if( b[i]==0 && isPrime((i+1)+ring[n-1]) )
{
b[i] = 1;
ring[n] = i+1;
if( primeRing(ring, b, n+1,LEN) )
return 1;
else
b[i] = 0;
}
return 0;
}
int isPrime(int n)
{
int i, t, f=1;
t = sqrt(n);
for(i=2; i<=t; i++)
if( n%i==0 )
{
f = 0;
break;
}
return f;
}
//13图着色
#include<stdio.h>
#define N 21
void main()
{ int r_color[N]={0};
int i,j;
int metro[N][N]
for(i=0;i<N;i++)
for(j=0;j<N;j++)
scanf("%d",&metro[i][j]);
color(metro,r_color,20);
for(i=1;i<=20;i++)
printf("%3d",r_color[i]);
}
int color(int metro[N][N],int r_color[N],int sum)
{
int i,j,k;
for(i=1;i<=sum;i++)
for(j=1;j<=4;j++)
{
r_color[i]=j;
for(k=1;k<i;k++)
if(metro[i][k]==1&&r_color[k]==r_color[i])
break;
if(k>=i)
break;
}
}
//图着色2
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
void main()
{ int i,j,N,*r_color,**metro;
scanf("%d",&N);
r_color=(int*)malloc(sizeof(int)*N);
metro=(int**)malloc(sizeof(int*)*N);
for(i=0;i<N;i++)
{ metro[i]=(int*)malloc(sizeof(int)*N);}
for(i=0;i<N;i++)
r_color[i]=0;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
scanf("%d",&metro[i][j]);
color(metro,r_color,20);
for(i=1;i<=20;i++)/*输出着色方案*/
printf("%3d",r_color[i]);
}
int color(int metro[N][N],int r_color[N],int sum)
{
int i,j,k;
for(i=1;i<=sum;i++)/*检查所有城市*/
for(j=1;j<=4;j++)/*对每个城市尝试4种颜色的着色方案*/
{
r_color[i]=j;/*尝试着色*/
for(k=1;k<i;k++)/*检查是否与相邻城市颜色相同*/
if(metro[i][k]==1&&r_color[k]==r_color[i])
break;/*相同则跳出，此时有k<i，则下面条件不成立，继续尝试下一种颜色*/
if(k>=i)/*若不相同，则使用当前颜色，并检查下一个城市*/
break;
}
}
//14批处理作业调度问题
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 1000
int visited[MAX]={0};
int t[MAX+1][2]={0};
int min_time=MAX;
int Fa=0,Fb=0;
int f=0;
int n=0;
int path[MAX][MAX]={0};
int count=1;
int order=1;
int best_choice=0;
int FACT=0;
void back_task(int num);
int fact(int n);
int main()
{ int i,m,j;
scanf("%d",&n);
FACT=fact(n-1);
for(i=1;i<=n;i++)
{
scanf("%d %d",&t[i][0],&t[i][1]);
}
back_task(1);
printf("\nThe minimum time is :%d",min_time);
printf("\n\nThe best choice is:");
for(j=1;j<=n;j++)
printf("%d ",path[best_choice][j]);
getch();
}
void back_task(int num)
{
int i=1,temp;
if(num>n)
{
if(f<min_time)
{
min_time=f;
best_choice=count;
}
count++;
return ;
}
for(i=1;i<=n;i++)
{
if(visited[i]==0 && f<min_time)
{
if(order==1)
{
for(temp=count;temp<count+FACT;temp++)
{
path[temp][order]=i;
}
}
path[count][order++]=i;
visited[i]=1;
Fa+=t[i][0];
temp=Fb;
if(Fa<Fb)
Fb+=t[i][1];
else
Fb=Fa+t[i][1];
f+=Fb;
back_task(num+1);
visited[i]=0;
Fa-=t[i][0];
f-=Fb;
Fb=temp;
order--;
}
}
}
int fact(int n)
{
if(n==1)
return 1;
else
return n*fact(n-1);
}
//15.01背包
#include<stdio.h>
int w[100],p[100];
int c,n,cw=0,cp=0,bestp=0,i;
int x[100]={0};
void try(int k)
{ if(k>n)
{ if(bestp<cp)
bestp=cp;
}
else
{ x[k]=1;
cw=cw+w[k];
cp=cp+p[k];
if(cw<=c)
try(k+1);
x[k]=0;
cw=cw-w[k];
cp=cp-p[k];
if(cw<=c)
try(k+1);
}
}
main()
{ scanf("%d",&n);
scanf("%d",&c);
for(i=0;i<n;i++)
scanf("%d %d",&w[i],&p[i]);
try(1);
printf("%d\n",bestp);
}
//1欧几里德算法
#include<stdio.h>
int main()
{
阅读背景：
C语言编写的一些上机题目代码，里面有比较基础的题目
来源：互联网
分享到：
