//此題重在理解兩個數相乘的算法,
4
#include <stdio.h>
5#include <stdlib.h>
6#include <string.h>
7#define MAXSIZE 201
8int main()
9
{
10
char line1[MAXSIZE];
11 char line2[MAXSIZE];
12 int a1[MAXSIZE];
13 int a2[MAXSIZE];
14 int product[MAXSIZE];
15
16 while ( scanf ("%s%s", line1, line2) != EOF )
17
{
18 int len1, len2;
19 len1 = strlen (line1);
20 len2 = strlen (line2);
21
22 memset (a1, 0, sizeof (a1));
23 memset (a2, 0, sizeof (a2));
24 memset (product, 0, sizeof (product));
25
26 //對負數的處理
27 if ( line1[0] == '-' || line2[0] == '-' )
28 return 0;
29 //對 0 和 其它數相乘的處理
30 int mark = 0;
31 if ( ( !strcmp (line1,"0") ) || ( !strcmp (line2, "0") ) )
32 {
33 printf ("%d", 0);
34
}
35
36 //將字符數轉化為數字
37 int j = 0;
38 for (int i = len1 - 1; i >= 0; i--)
39 {
40 a1[j++] = line1[i] - '0';
41 }
42 int k = 0;
43 for (int i = len2 - 1;i >= 0; i--)
44 {
45 a2[k++] = line2[i] - '0';
46 }
47
48 //乘法算法
49 for (int i = 0; i < len2; i++)
50 for (int j = 0; j < len1; j++)
51 {
52 product[i + j] += a1[j] * a2[i];
53 }
54
55 //處理進位
56 for (int i = 0; i < MAXSIZE; i++ )
57 {
58 if ( product[i] >= 10 )
59 {
60 product [i + 1] += product [i] / 10;
61 product [i] = product[i] % 10;
62 }
63 }
64
65 //輸出處理
66 bool target = false;
67 for (int i = MAXSIZE - 1; i >= 0; i--)
68 {
69 if (target)
70 printf ("%d", product[i]);
71 else if (product[i])
72 {
73 printf ("%d", product[i]);
74 target = true;
75 }
76 }
77 printf ("\n");
78 }
79 //system ("pause");
80 return 0;
81
}
82
以及特殊數據的考慮 ：如 含有 0 和 負數時
posted @
2010-08-09 13:08 雪黛依夢 閱讀(406) |
評論 (0) |
編輯 收藏
2//1.用字符數組輸入
3//2.字符轉化為數字進行計算
4//3.數組中下標相同的相加并存入到sum[]中
5//4.進位處理
6//5.存在前導 0 進行輸出處理 一定要注意最開始 0 的存儲位置 i = 2*MAXSIZE
7#include<stdio.h>
8#include<stdlib.h>
9#include<string.h>
10#define MAXSIZE 100
11int main()
12{
13 char line[MAXSIZE];
14 int a[MAXSIZE];
15 int sum[MAXSIZE + MAXSIZE];
16
17 memset (sum, 0, sizeof(sum));
18 while ( scanf ("%s",line) && strcmp (line, "0") ) //求和終止條件
19 {
20 while ( line[0] == '-')
21 return 0;
22
23 memset (a, 0, sizeof(a));
24
25 //將字符數轉化為數字
26 int j = strlen(line);
27 for (int i = j - 1; i >= 0; i--)
28 {
29 a[j-1-i] = line[i] - '0';
30 }
31
32 //將各組數據相加到sum數組中
33 for (int i = 0; i <= MAXSIZE; i++)
34 {
35 sum[i] += a[i];
36 }
37 }
38
39 //對sum【】進行進位的處理
40 for ( int i = 0; i <= 2*MAXSIZE; i++ )
41 {
42 if ( sum[i] >= 10 )
43 {
44 sum[i+1] += (sum[i] / 10);
45 sum[i] = sum[i] % 10;
46
47 }
48 }
49
50 //進行輸出處理
51 bool target = false;
52 for ( int i = 2*MAXSIZE ; i >= 0; i--)
53 {
54 if (target)
55 printf ("%d", sum[i]);
56 else if ( sum[i] )
57 {
58 printf ("%d", sum[i]);
59 target = true;
60 }
61 }
62 printf ("\n");
63 //system("pause");
64 return 0;
65}
66
posted @
2010-08-09 13:07 雪黛依夢 閱讀(290) |
評論 (0) |
編輯 收藏
其實這道題只要找到了解題的切入口是很簡單的 ：出現不等號必然是由假幣引起的，所以假幣在不等式兩邊出現的次數必然等于所輸入的不等號的數。 通過tag 數組記錄硬幣是否在等號兩邊出現過，這樣的被標記為1,遍歷時跳過，沒有被標記為 1 的可能是假幣，再看數組num中記錄的i硬幣在不等式出現的次數是否等于不等號的次數
1#include <stdio.h>
2#include <stdlib.h>
3#define MAX 1001
4#define OK 1
5
6int tag[MAX]; //將出現了等號的(即真幣)排除 標記為1 遍歷時跳過
7int num[MAX]; //記錄下標為i的硬幣在不等式的兩邊出現的次數
8
9int main ()
10{
11
12 int coin[MAX]; //訪問時下標的中介
13 int N, k, pi, count ;
14 char c;
15
16 while ( scanf ("%d%d", &N, &k) != EOF )
17 {
18 count = 0; //記錄接下來的 k 次稱量中有多少次出現了不等號
19
20 for ( int i = 0; i < k; i ++) // k 次的稱量記錄
21 {
22 scanf ("%d", &pi);
23 for (int j = 0; j < 2 * pi; j ++)
24 {
25 scanf ("%d", &coin[j]);
26 }
27
28 getchar ();
29
30 c = getchar ();
31
32 for (int i = 0; i < 2 * pi; i ++)
33 {
34 if (c == '=')
35 tag[coin[i]] = 1;
36
37 else if (c == '<')
38 {
39 count ++;
40 for (int j = 0; j < pi; j ++)
41 {
42 num[coin[j]]--;
43 }
44 for (int j = pi; j < 2 * pi; j++)
45 {
46 num[coin[j]]++;
47 }
48 }
49
50 else
51 {
52 count ++;
53 for (int j = 0; j < pi; j ++)
54 {
55 num[coin[j]]++;
56 }
57 for (int j = pi; j < 2 * pi; j++)
58 {
59 num[coin[j]]--;
60 }
61 }
62 }
63
64 }
65
66 int mark = 0;
67 int temp ;
68 for (int i = 1; i <= N; i ++)
69 {
70 if (tag[i] == 1) //表示為真幣，不可能
71 continue;
72
73 if (num[i] == count || num[i] == -count) //如果硬幣在不等式的兩邊出現的次數等于不等號數為假幣
74 {
75 mark ++;
76 temp = i;
77 }
78 }
79
80 if (mark == 1) // 假幣只有一個
81 {
82 printf ("%d\n", temp);
83 }
84
85 else
86 printf ("%d\n",0);
87
88 }
89
90 return 0;
91}
92
posted @
2010-08-09 13:06 雪黛依夢 閱讀(290) |
評論 (0) |
編輯 收藏
摘要: 1.用蠻力解這道題也能AC，雖然測試數據能過但是還是AC了，然后看了一些特殊的數據 24 29 34 2 21251，在修改了一下自己的代碼加了一個else語句，就AC了，可是自己都有點不太明白。暈了！！！！
1#include <stdio.h&g...
閱讀全文
posted @
2010-08-06 15:58 雪黛依夢 閱讀(186) |
評論 (0) |
編輯 收藏
n%3=2,n%5=3,n%7=2 且3，5，7互質 求
n的值：
使5×7被3除余1，用35×2=70；
使3×7被5除余1，用21×1=21；
使3×5被7除余1，用15×1=15。
（70×2+21×3+15×2）%（3×5×7）=23
所以n = 23
posted @
2010-08-06 14:50 雪黛依夢 閱讀(298) |
評論 (1) |
編輯 收藏其實這個題的思路和簡單：找到最短的一個串，然后再找到他所有的子串和子串的逆串和所給的串進行匹配。
但是如果不直接調用string.h的函數實現這些功能，我自己就不知道做；
感覺String.h 有好多功能自己不了解，像strstr() strncpy() strrev()可是poj系統不支持這個函數
1#include <stdio.h>
2#include <string.h>
3char str[100][101];
4
5int t, n;
6void strrev (char *revString)
7{
8 int revLen = strlen (revString);
9 char temp[101];
10
11 int i;
12 for ( i = 0; i < revLen; i ++)
13 {
14 temp[i] = revString[revLen - i - 1];
15 }
16 temp [i] = '\0';
17 strcpy (revString, temp);
18}
19
20int searchSubString (char *source)
21{
22 char minSubString[101];
23 char minrevSubString[101];
24
25 int minSubStringLen = strlen (source);
26 int sourceLen = strlen (source);
27
28 while (minSubStringLen)
29 {
30 for (int i = 0; i <= sourceLen - minSubStringLen; i ++)
31 {
32 bool tag = true;
33 strncpy (minSubString, source + i, minSubStringLen);
34 strncpy (minrevSubString, source + i, minSubStringLen);
35
36 minSubString[minSubStringLen] = minrevSubString[minSubStringLen] = '\0';
37
38 strrev (minrevSubString);
39
40 for (int i = 0; i < n; i ++)
41 {
42 if ( strstr (str[i], minSubString) == NULL && strstr (str[i], minrevSubString) == NULL )
43 {
44 tag = false;
45 break;
46 }
47 }
48
49 if (tag)
50 return minSubStringLen;
51 }
52 minSubStringLen --;
53 }
54
55 return 0;
56}
57
58int main ()
59{
60
61 char minStr[101];
62
63 scanf ("%d", &t);
64 while ( t != 0 )
65 {
66 scanf ("%d", &n);
67
68 int minStrlen = 100;
69 for (int i = 0; i < n; i ++)
70 {
71 scanf ("%s", str[i]);
72 if ( ( strlen(str[i]) ) < minStrlen )
73 {
74 strcpy(minStr, str[i]);
75 minStrlen = strlen (str[i]);
76 }
77 }
78
79 int minSubLen = searchSubString (minStr);
80 printf ("%d\n", minSubLen);
81
82 t --;
83 }
84 return 0;
85}
posted @
2010-08-06 11:50 雪黛依夢 閱讀(325) |
評論 (0) |
編輯 收藏
WA了一次，主要是自己把continue寫成了break，所以遇到素數時下面的輸就終止了；
解題思路：如n是素數就直接打印出來，如果不是素數(通過訪問0--n下標的tag數組判斷n是否為素數，再n依次對素數表prime【】求余求模分解n)，就利用打印出來的素數表進行不斷地求余、求模分解；直到n為1；
一定要注意怎么輸出哦！！！
1#include <stdio.h>
2#include <stdlib.h>
3#define MAXSIZE 65535
4int tag[MAXSIZE + 1];
5int prime[MAXSIZE];
6int cn ;
7
8void is_prime ()
9{
10 for (int i = 2; i < MAXSIZE + 1; i ++)
11 {
12 if ( !tag[i] )
13 prime[cn++] = i;
14 for ( int j = 0 ; (j < cn) && ( i*prime[j] < MAXSIZE + 1 ) ; j ++ )
15 {
16 tag[ i * prime[j] ] = 1;
17 if ( i % prime [j] == 0)
18 break;
19 }
20 }
21}
22
23int main ()
24{
25 is_prime ();
26 int n;
27 int elem[60000];
28 while ( scanf ("%d", &n) != EOF )
29 {
30 if ( !tag[n] )
31 {
32 printf ("%d\n",n);
33 continue;
34 }
35 else
36 {
37 int j = 0;
38 for (int i = 0; i < cn && n != 1 ; i ++)
39 {
40 while ( n % prime[i] == 0 )
41 {
42 elem[j] = prime[i];
43 n = n / prime[i];
44 j ++;
45 }
46 }
47 printf ("%d", elem[0]);
48 for (int m = 1; m < j; m++)
49 {
50 printf ("*%d",elem[m]);
51 }
52 printf ("\n");
53 }
54 }
55 //system ("pause");
56 return 0;
57}
58
posted @
2010-08-06 09:19 雪黛依夢 閱讀(422) |
評論 (0) |
編輯 收藏我暈了！這么水的題，我居然WA了N 次，，，就是自己沒有理解好題意最后還對ENDOFINPUT進行了輸出處理
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4int main ()
5{
6
char start[11];
7
char end[4];
8
char cipher[201];
9
int len;
10
11
scanf ("%s", start);
12
while ( strcmp (start, "ENDOFINPUT") )
13
{
14
getchar ();
15
16
gets (cipher);
17
18
getchar ();
19
20
scanf ("%s", end);
21
22
//對密文進行解密
23
len = strlen (cipher);
24
for (int i = 0; i < len; i ++)
25
{
26
if ( ('A' <= cipher[i]) && ( cipher[i] <= 'Z') )
27
{
28
if ( 70 <= cipher[i] && cipher[i] <= 90)
29
printf ("%c", cipher[i] - 5);
30
else
31
printf ("%c", cipher[i] + 21);
32
}
33
else
34
printf ("%c", cipher[i]);
35
}
36
printf ("\n");
37
scanf ("%s", start);
38
}
39
//printf ("ENDOFINPUT\n"); 畫蛇添足
40
//system ("pause");
41
return 0;
42
}
43
posted @
2010-08-05 16:00 雪黛依夢 閱讀(472) |
評論 (0) |
編輯 收藏這題開始也不知道做，是看了別人的才AC的，感覺數論好高深的。
分析易知：x、y是大于n的；
設y = n + k ( k > = 1),則：x = n 2 / k + n;
所以本題關鍵是找到使x 為整數的k的個數，
由定理：任何一個正整數都可以表示成兩個素數之積，所以本題就被轉化成了求n ^2的素因子個數；
n = p1^e1 * p2^e2 * ......*pr^er; 其中p是< n 的素數
那么n 的素因子個數 (e1 + 1) * (e2 + 1) * (e3 + 1)*......
所以：n ^2的素因子數是 (2*e1+1) * (2*e2+1)* (2*e3+1)......
1
//為什么要把范圍縮小到n的方根之內呢？？ 2
#include <stdio.h>
3
#include <stdlib.h>
4
#include <math.h>
5
# define MAXSIZE 40000
6
7
int prime[MAXSIZE];
8
int primeElem[MAXSIZE];
9
int cn; //0 -- n內素數的個數
10
11
void is_prime ( )
12
{
13
for (int i = 2; i < MAXSIZE; i ++)
14
{
15
if ( !prime [i] )
16
{
17
for (int j = 2 * i; j < MAXSIZE; j += i)
18
{
19
prime [j] = 1;
20
}
21
//把 0 -- n 內的素數存到數組中
22
primeElem[cn ++] = i;
23
}
24
}
25
}
26
27
int main ()
28
{
29
int m, n;
30
is_prime( );
31
32
while ( scanf ("%d", &m) != EOF )
33
{
34
for ( int i = 0; i < m; i ++)
35
{
36
scanf ("%d", &n);
37
38
//找到 n 以內的 素因子
39
int product = 1;
40
int flag = 0;
41
for ( int j = 0; j < cn; j ++)
42
{
43
flag = (int) sqrt (n * 1.0) + 1; //n 的 方根
44
if ( primeElem[j] > flag ) //p1、p2、p3 這些素數要 < n
45
break;
46
int e = 0;
47
while ( n % primeElem[j] == 0 )
48
{
49
e ++;
50
n /= primeElem[j];
51
}
52
product *= ( 1 + 2 * e);
53
}
54
if ( n > 1 )
55
product *= 3; //這步要注意，最后有可能剩下的n本身就是原來n的素因子 ????
56
printf ("Scenario #%d:\n", i+1);
57
printf ("%d\n", ( product + 1 )/2 );
58
59
printf ("\n");
60
}
61
}
62
//system ("pause");
63
return 0;
64
}
65
posted @
2010-08-05 15:18 雪黛依夢 閱讀(1375) |
評論 (0) |
編輯 收藏