把之前拿走的通過遞歸的形式補回來： 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 雪黛依夢 閱讀(231) |
評論 (0) |
編輯 收藏
此題只要抓住一個突破口即可：第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 雪黛依夢 閱讀(485) |
評論 (0) |
編輯 收藏
這類問題一般都有固定的公式，告訴大家一個技巧：二維的一般是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 雪黛依夢 閱讀(193) |
評論 (0) |
編輯 收藏
(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 雪黛依夢 閱讀(377) |
評論 (0) |
編輯 收藏 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 雪黛依夢 閱讀(309) |
評論 (0) |
編輯 收藏
這道題雖然求遞推公式很簡單，可是我卻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 雪黛依夢 閱讀(231) |
評論 (0) |
編輯 收藏重點：
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 雪黛依夢 閱讀(726) |
評論 (0) |
編輯 收藏//思路：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 雪黛依夢 閱讀(629) |
評論 (0) |
編輯 收藏 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 雪黛依夢 閱讀(593) |
評論 (0) |
編輯 收藏
摘要: //思路: 大數問題的處理，通常都是以字符串的形式讀入，再將字符轉化為數字進行處理//因為除法運算的實質是：被除數能夠減去除數的多少倍；以7546 / 23 為例// 開始時：7546 - 23 的 100倍可以減 3 次 等于 646 ；所以商增加 300// &nb...
閱讀全文
posted @
2010-08-09 13:11 雪黛依夢 閱讀(1369) |
評論 (0) |
編輯 收藏