- //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);
- }
来源: http://lib.csdn.net/article/datastructure/49574