C++博客-大成至圣

C语言质因数分解

姚冰 — Wed, 05 Jan 2011 16:31:00 GMT

1#include <stdio.h>
2#define MAX 200
3
4typedef struct
5{
6    int num;
7    int x[MAX];
8    int y[MAX];
9} fac;
10
11void factorization(fac *a, int x) // 质因数分解
12{
13    int i, count;
14
15    if (x <= 0)
16    {
17        a->num = 0;
18        return;
19    }
20
21    if (x == 1)
22    {
23        a->num = 1;
24        a->x[0] = a->y[0] = 1;
25        return;
26    }
27
28    a->num = 0;
29
30    for (i = 2; i * i <= x; i++)
31    {
32        count = 0;
33
34        while (x % i == 0)
35        {
36            x /= i;
37            count++;
38        }
39
40        if (count != 0)
41        {
42            a->x[a->num] = i;
43            a->y[a->num++] = count;
44        }
45    }
46
47    if (x != 1)
48    {
49        a->x[a->num] = x;
50        a->y[a->num++] = 1;
51    }
52}
53
54int main()
55{
56    int x, i;
57    fac f;
58
59    while (scanf ("%d", &x) != EOF)
60    {
61        factorization(&f, x);
62
63        if (f.num <= 0)
64        {
65            printf("Factorization Error!\n");
66            continue;
67        }
68
69        printf("%d = %d ^ %d", x, f.x[0], f.y[0]);
70        for (i = 1; i < f.num; i++)
71            printf(" * %d ^ %d", f.x[i], f.y[i]);
72        printf("\n");
73    }
74
75    return 0;
76}

姚冰 2011-01-06 00:31 发表评论

C语言高精度运算函数库

姚冰 — Wed, 05 Jan 2011 16:15:00 GMT

摘要: 1#include 2#include 3#define MAX 200 4 5typedef struct 6{ &nbs... 阅读全文

姚冰 2011-01-06 00:15 发表评论

表达式模板

姚冰 — Fri, 17 Apr 2009 13:00:00 GMT

摘要: /**//***************************表达式模板****************************/#include#include#includeusing namespace std;int signMap[7][7]={ &... 阅读全文

姚冰 2009-04-17 21:00 发表评论

计算几何之线段、直线、圆

姚冰 — Tue, 14 Apr 2009 02:58:00 GMT

摘要: 1#include 2#include 3 4const double eps=1e-6; 5 6//点(x,y) 7typedef struc... 阅读全文

姚冰 2009-04-14 10:58 发表评论

P02: 完全背包问题

姚冰 — Tue, 07 Apr 2009 12:16:00 GMT

摘要: 题目有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。基本思路这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照... 阅读全文

姚冰 2009-04-07 20:16 发表评论

P01:01背包问题

姚冰 — Mon, 06 Apr 2009 03:43:00 GMT

摘要: 题目有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。基本思路这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是： f[i][v]=max{f[i-1][v],f[i-1][v-c[i... 阅读全文

姚冰 2009-04-06 11:43 发表评论