posts - 99,  comments - 8,  trackbacks - 0
 
poj grids 2980 大数的乘法
//此题重在理解两个数相乘的算法,

 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 雪黛依梦 阅读(371) | 评论 (0) | 编辑 收藏
poj grids 2981 大数的加法
 
 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 雪黛依梦 阅读(257) | 评论 (0) | 编辑 收藏
poj 1029 蛮力法 || 标记法
其实这道题只要找到了解题的切入口是很简单的 ：出现不等号必然是由假币引起的，所以假币在不等式两边出现的次数必然等于所输入的不等号的数。  通过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 雪黛依梦 阅读(260) | 评论 (0) | 编辑 收藏
poj 1006 蛮力 中国剩余定理
     摘要: 1.用蛮力解这道题也能AC，虽然测试数据能过但是还是AC了，然后看了一些特殊的数据 24 29 34 2           21251，在修改了一下自己的代码加了一个else语句，就AC了，可是自己都有点不太明白。晕了！！！！  1#include <stdio.h&g...  阅读全文
posted @ 2010-08-06 15:58 雪黛依梦 阅读(169) | 评论 (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 雪黛依梦 阅读(266) | 评论 (1) | 编辑 收藏
poj Grids 2744

其实这个题的思路和简单：找到最短的一个串，然后再找到他所有的子串和子串的逆串和所给的串进行匹配。
但是如果不直接调用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 雪黛依梦 阅读(296) | 评论 (0) | 编辑 收藏
hud 1164 数论 将一个数分解成素因子之积
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 雪黛依梦 阅读(388) | 评论 (0) | 编辑 收藏
poj 1298 字符串的处理问题

我晕了！这么水的题，我居然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 雪黛依梦 阅读(446) | 评论 (0) | 编辑 收藏
数论 hdu 1299 关键是如何求得一个数n的素因子个数

这题开始也不知道做，是看了别人的才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
 7int prime[MAXSIZE];
 8int primeElem[MAXSIZE];
 9int cn;          //0 -- n内素数的个数 
10
11void 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
27int 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 雪黛依梦 阅读(1342) | 评论 (0) | 编辑 收藏
仅列出标题
共10页: First 2 3 4 5 6 7 8 9 10 
Copyright ©2024 雪黛依梦 Powered By: 博客园 模板提供：沪江博客
<2024年5月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

常用链接

留言簿(4)

随笔分类

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜