posts - 99,  comments - 8,  trackbacks - 0
 
hdu 2042 简单递归

把之前拿走的通过递归的形式补回来： n  - 1 时是 n 时的2 倍，但是后来补回来了一个所以多加了2  个

#include <stdio.h>
#include <stdlib.h>

int main ()
{
    int ff[31];
    int n, a;
    
    ff[1] = 4;
    ff[2] = 6;
    for (int i = 3; i < 31; i ++)
    {
        ff[i] =  ( ff[i - 1] - 1 ) * 2 ;
    }
    
    while ( scanf ("%d", &n) != EOF )
    {
          for (int i = 0; i < n; i ++)
          {
              scanf ("%d", &a);
              printf ("%d\n",ff[a]); 
          }
    }
    return 0;
}
posted @ 2010-08-13 20:08 雪黛依梦 阅读(219) | 评论 (0) | 编辑 收藏
hdu 2018 简单的递归
此题只要抓住一个突破口即可：第n 年的数目是前 n - 1 年的所有牛加上 n - 3 年前的小牛肯定会再产生一头
找好递归的出口是关键
#include <stdio.h>
#include <stdlib.h>


int main ()
{
    int n;
    int a[55];
    a[1] = 1;
    a[2] = 2;
    a[3] = 3;
    //a[4] = 4;
    for (int i = 4; i < 55; i ++)
    {
        a[i] = a[i - 1] + a[i - 3];
    }
    
    while ( scanf ("%d", &n) && n!= 0 )
    {
          printf ("%d\n", a[n]);
    }
    return 0;
}
posted @ 2010-08-13 16:36 雪黛依梦 阅读(469) | 评论 (0) | 编辑 收藏
hdu 1290 将实际问题转化为数学模型
这类问题一般都有固定的公式，告诉大家一个技巧：二维的一般是an^2+bn+c,三维的一般是an^3+bn^2+cn+d.

用带定系数法求出各个系数就OK了，不用想破脑筋找规律。。。。。。
(n * n * n + 5*n) / 6 + 1;

 1#include <stdio.h>
 2#include <stdlib.h>
 3int main ()
 4{
 5    int n;
 6    __int64 result;
 7    while ( scanf ("%d", &n) != EOF )
 8    {
 9          result = ( n * n * n + 5 * n) / 6 + 1;
10          printf ("%I64d\n", result);    
11    }
12    return 0;
13}
14
posted @ 2010-08-09 21:27 雪黛依梦 阅读(179) | 评论 (0) | 编辑 收藏
HDU 1290
 

(1) n条直线最多分平面问题

       题目大致如:n条直线，最多可以把平面分为多少个区域。

       析:可能你以前就见过这题目，这充其量是一道初中的思考题。但一个类型的题目还是从简单的入手，才容易发现规律。当有n-1条直线时，平面最多被分成了f（n-1）个区域。则第n条直线要是切成的区域数最多，就必须与每条直线相交且不能有同一交点。 这样就会得到n-1个交点。这些交点将第n条直线分为2条射线和n-2条线断。而每条射线和线断将以有的区域一分为二。这样就多出了2+（n-2）个区域。

          故：f(n)=f(n-1)+n

                       =f(n-2)+(n-1)+n

                       ……

                       =f(1)+1+2+……+n

                       =n(n+1)/2+1


         (2) 折线分平面（hdu2050）

        根据直线分平面可知，由交点决定了射线和线段的条数，进而决定了新增的区域数。当n-1条折线时，区域数为f（n-1）。为了使增加的区域最多，则折线的两边的线段要和n-1条折线的边，即2*（n-1）条线段相交。那么新增的线段数为4*（n-1），射线数为2。但要注意的是，折线本身相邻的两线段只能增加一个区域。

       

        故：f(n)=f(n-1)+4(n-1)+2-1

                       =f(n-1)+4(n-1)+1

                      =f(n-2)+4(n-2)+4(n-1)+2

                      ……

                      =f(1)+4+4*2+……+4(n-1)+(n-1)   

                      =2n^2-n+1

       (3) 封闭曲线分平面问题

       题目大致如设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。

        析：当n-1个圆时，区域数为f(n-1).那么第n个圆就必须与前n-1个圆相交，则第n个圆被分为2（n-1）段线段，增加了2（n-1）个区域。

  

              故： f(n)=f(n-1)+2(n-1)     

                              =f(1)+2+4+……+2(n-1)

                              =n^2-n+2

           (4)平面分割空间问题（hdu1290）

           由二维的分割问题可知，平面分割与线之间的交点有关，即交点决定射线和线段的条数，从而决定新增的区域数。试想在三维中则是否与平面的交线有关呢？当有n-1个平面时，分割的空间数为f（n-1）。要有最多的空间数，则第n个平面需与前n-1个平面相交，且不能有共同的交线。即最多有n-1 条交线。而这n-1条交线把第n个平面最多分割成g（n-1）个区域。（g（n）为（1）中的直线分平面的个数 ）此平面将原有的空间一分为二，则最多增加g（n-1）个空间。

         

         故：f=f(n-1)+g(n-1)     ps:g(n)=n(n+1)/2+1

                    =f(n-2)+g(n-2)+g(n-1)

                    ……

                   =f(1)+g(1)+g(2)+……+g(n-1)

                  =2+(1*2+2*3+3*4+……+(n-1)n)/2+（n-1）

                  =(1+2^2+3^2+4^2+……+n^2-1-2-3-……-n )/2+n+1

                 =(n^3+5n)/6+1
posted @ 2010-08-09 21:03 雪黛依梦 阅读(359) | 评论 (0) | 编辑 收藏
hdu 2046 简单递归题
 1#include <stdio.h>
 2#include <stdlib.h>
 3int main ()
 4{
 5    int n;
 6    __int64 a[51];
 7    while ( scanf ("%d", &n) != EOF )
 8    {
 9          a[1] = 1; a[2] = 2;  
10          for (int i = 3; i <= n; i ++)
11          {
12              a[i] = a[i - 2] + a[i - 1];
13          }
14          
15          printf ("%I64d\n", a[n]);
16    }
17    //system ("pause");
18    return 0;
19}
20
posted @ 2010-08-09 20:17 雪黛依梦 阅读(302) | 评论 (0) | 编辑 收藏
hdu 1465 递归 错排问题
这道题虽然求递推公式很简单，可是我却WA了几次：
1.递归问题中如果之直接用公式很容易栈溢出，用数组保留相应的值
2.由递归得到的最终结果很大所以在定义数据类型的时候要注意范围，否则正确的值
 1#include <stdio.h>
 2#include <stdlib.h>
 3int main ()
 4{
 5    int i , n;
 6    __int64 a[21];
 7    
 8    a[1] = 0; a[2] = 1; 
 9       
10    while ( scanf ("%d", &n) != EOF )
11    {
12          
13          for (int i = 3; i <= n; i ++)
14          {
15              a[i] = (i - 1)*(a[i - 1] + a[i - 2]);
16          }
17          
18          printf ("%I64d\n", a[n]);
19    }
20    //system ("pause");
21    return 0;
22}
23
posted @ 2010-08-09 20:07 雪黛依梦 阅读(215) | 评论 (0) | 编辑 收藏
hdu 2050 折线分割平面

重点：http://hi.baidu.com/%BA%B2%C4%AB%C7%F3%CA%AF/blog/item/95f5fd2d8a40a8321f308984.html
 1#include <stdio.h>
 2#include <stdlib.h>
 3int main ()
 4{
 5    int n, i, num;
 6    
 7    while ( scanf ("%d", &i) != EOF )
 8    {
 9          for (int j = 0; j < i; j++)
10          {
11              num = 0;
12              scanf ("%d", &n);
13              num = 2 * n * n - n + 1;
14              printf ("%d\n", num);
15          }
16    }
17    return 0;
18}
19
思路：分析易知直线分割平面的关系：an= (n*n + n + 2) / 2;

拓展：曲线分割平面
问题的提出：
    设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。
F(1)=2
F(n)=F(n-1)+2(n-1)
posted @ 2010-08-09 18:08 雪黛依梦 阅读(683) | 评论 (0) | 编辑 收藏
poj 1503 任意精度计算 求 R 的 n 次幂

//思路：1.调用函数change() 将小数 s 转化成去掉小数点的整数 s1 并且返回得到小数点的位置。
//      2.调用函数mu1()用大数乘法模拟整数运算，并将相乘的结果放在s2中，返回s2和是进行下面的 n -1次相乘
//      3.在主函数里面通过已知的小数点的位置，利用数值关系输出
//      4.注意小数点前没有前导0，小数点后面没有尾0。

//难点：for ( int i = 1; i < n; i ++)     mu1 (s1,s2);

 1             
 2#include <stdio.h>
 3#include <stdlib.h>
 4#include <string.h>
 5#define LENGTH 6  //小数的位数（含小数点） 
 6
 7//将字符转化为数字 
 8unsigned int change (char s[LENGTH], unsigned int s1[LENGTH - 1])
 9{
10     int ss[LENGTH - 1];  //ss 放未逆置的整数 
11     memset (ss, 0, sizeof(ss));
12     
13     int k = 0 ;
14     for (int i = 0; i < LENGTH && s[i]; ++i)  //考虑特殊数据如：0.0001 
15     {
16         if (s[i] != '.')
17            ss[k++] = s[i] - '0';
18     } 
19     for (int j = 0;j < LENGTH - 1; j++)
20     {
21         s1[j] = ss[LENGTH - 2 - j];  
22     }
23     
24     int m = 0;
25     while ( (s[m] != '.') && s[m] )
26           ++m; 
27           return LENGTH - 1 - m;   //小数点位数 
28} 
29
30//大数乘法运算 
31//函数返回 s2 
32void mu1 (unsigned int s1[LENGTH - 1],unsigned int s2[130])
33{
34     int ss[130];
35     memset ( ss, 0, sizeof(ss) );
36     
37     for ( int i = 0; i < LENGTH - 1; i++)
38         for (int j = 0;j < 130; j++)  //难点:因为返回新的s2之后位数会增加 最多时 5* 25 = 125 
39         ss [i + j] += s1[i] * s2[j];
40     
41     //将 两个大数相乘得的积ss中进行进位处理后放到s2 中  
42     int c = 0;
43     for (int i = 0;i < 130;i++)
44     {
45         s2[i] = (c + ss[i]) % 10;
46         c = (c + ss[i]) / 10;
47     } 
48}
49
50int main()
51{
52    int n;
53    char s[LENGTH];  //要处理的幂 R 
54    unsigned int s1[LENGTH - 1];  //将 R 转化成数字 
55    unsigned int s2[130];
56     
57    while(scanf ("%s%d", s, &n) != EOF)
58    {
59        memset (s1, 0, sizeof (s1));
60        memset (s2, 0, sizeof (s2)); 
61        
62        int j = change (s, s1);      //得到小数点所在位置 
63        change (s,s2);              //得到s2 和 s1 进行幂运算 
64        for ( int i = 1; i < n; i ++)
65            mu1 (s1,s2); 
66        
67        //在s2中前面的代表小数位，后面的代表整数位，
68        //所以关键是通过数值关系找到小数点的位置
69      
70      
71         //例：0.1010  * 0.1010 = 0.01020100  
72        int m = 129;//去掉前导0 
73        while ( (!s2[m]) && m)
74        --m;
75        
76        int k = 0; //去掉尾0                       
77        while ( ( !s2[k] ) && (k < 130))                                                           
78        ++k;
79        
80        //输出整数位 
81        for (int i = m; i >= n * j; i--)
82            printf ("%d",s2[i]);
83            
84        //输出小数点
85        if ( j && n * j >= k + 1) 
86        printf (".");
87        
88        for (int i = n*j -1; i >= k; --i)
89        printf ("%d", s2[i]);
90        printf ("\n");
91    }
92    
93    return 0;
94   // system ("pause");   
95}
96
posted @ 2010-08-09 13:21 雪黛依梦 阅读(610) | 评论 (0) | 编辑 收藏
poj 1503 多个大数相加求和
 1
 2#include<stdio.h>
 3#include<stdlib.h>
 4#include<string.h>
 5#define MAXSIZE 101
 6int main()
 7{
 8    char line[MAXSIZE];
 9    int sum[MAXSIZE + 1];
10    
11    memset (sum, 0, sizeof(sum));
12   
13    while (  scanf ("%s",line) && strcmp (line, "0") )  //求和终止条件 
14    {
15    //处理负数情况 
16      while ( line[0] == '-') 
17             return 0;
18      
19      //将字符数转化为数字 ，并且相加存到sum【】数组中 
20      int j = strlen(line);
21      for (int i = j - 1; i >= 0; i--)
22      {
23          sum[j-1-i] += (line[i] - '0');
24      } 
25    }
26    
27    //对sum【】进行进位的处理 
28    for ( int i = 0; i <= MAXSIZE; i++ )
29    {
30        if ( sum[i] >= 10 )
31        {
32             sum[i+1] += (sum[i] / 10);
33             sum[i] = sum[i] % 10;
34        }
35    } 
36    /*int c = 0;
37    for (int i = 0; i < MAXSIZE; i++)
38    {
39        c += sum[i];
40        sum[i] = c % 10;
41        c = c / 10;
42    }
43    
44    for (int i = MAXSIZE; i >= 0; i--)
45    {
46        if (sum[i] != 0)
47        printf ("%d", sum[i]);
48    }*/
49    
50    //进行输出处理
51    bool target = false;
52    for ( int i = 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:12 雪黛依梦 阅读(575) | 评论 (0) | 编辑 收藏
poj grids 2737 大数除法
     摘要: //思路: 大数问题的处理，通常都是以字符串的形式读入，再将字符转化为数字进行处理//因为除法运算的实质是：被除数能够减去除数的多少倍；以7546 / 23 为例//  开始时：7546 - 23  的 100倍可以减 3 次 等于 646 ；所以商增加 300//         &nb...  阅读全文
posted @ 2010-08-09 13:11 雪黛依梦 阅读(1339) | 评论 (0) | 编辑 收藏
仅列出标题
共10页: First 2 3 4 5 6 7 8 9 10 
Copyright ©2024 雪黛依梦 Powered By: 博客园 模板提供：沪江博客
<2010年8月>
日一二三四五六
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(4)

随笔分类

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜