數的計數

Time Limit:1000MS  Memory Limit:65536K
Total Submit:394 Accepted:183

Description

要求找出具有下列性質數的個數（包括輸入的自然數n):
先輸入一個自然數n( n <= 1000),然后對此自然數按照如下方法進行處理：
（1）不作任何處理
（2）在它的左邊加上一個自然數，但該數不能超過原數的一半
（3）加上數后，繼續按此處理，直到不能再加自然數為止

Input

多個測試案例，每個測試案例
輸入一個自然數n

Output

輸出滿足以上條件的所有數的個數

Sample Input

6

 

Sample Output

6

 

Hint

對于6，滿足條件的數有
6
16
26
126
36
136

         這個題目也貼一下，記得書上也有這么個習題的！！
代碼如下：
        問題描述：在一塊電路板的上、下兩端分別有n個接線柱。根據電路設計，要求用導線(i,π(i)) 將上端接線柱i與下端接線柱π(i)相連，如下圖。其中，π(i),1≤ i <≤n,是｛1,2,…,n｝的一個排列。導線(I, π(i))稱為該電路板上的第i條連線。對于任何1 ≤ i ≤ j≤n,第i條連線和第j條連線相交的充要條件是π(i)> π(j).

在制作電路板時，要求將這n條線分布到若干個絕緣層上，在同一層上的連線不能相交。電路布線問題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。換句話說，該問題要求確定導線集Nets = ｛i，π(i)，1 ≤ i ≤ n｝的最大不想交子集。
         書上解決這個問題的時候用了很多集合的概念，我花了一上午的時間去理解，結果沒理解啥意思！！！最后還是結合遞歸式和代碼看懂他說的最優子結構性質這一段基本意思。。
         定義了一個Size[i][j]二維數組，代表從上端點1，下端點1到上端點i，下端點j之間的最優解。在這樣的定義下我們可以求得size[1][j],然后根據定義求得數組上其他值！！最后Size[n][n]就是所求解！！在遞推Size[i][j]時，要抓住i條線路在最優解內和不在最優解內做判斷。
代碼如下：

#include<windows.h>
#include<stdio.h>
#include<windef.h>
#include<string.h>
void MNS(int C[],int n,int size[][20])
{
    int i,j;
    for(j=0;j<C[1];j++)    //初始化
    {
        size[1][j]=0;
    }

    for(j=C[1];j<=n;j++)//初始化
    {
        size[1][j]=1;
    }

    for(i=2;i<n;i++)        //n>i>=2
    {
        for(j=0;j<C[i];j++)    //j<C[i]時第i條線路必然不在最優解內
            size[i][j]=size[i-1][j];

        for(j=C[i];j<=n;j++)
            size[i][j]=max(size[i-1][j],size[i-1][C[i]-1]+1);//取第i條線路在最優解內和不在最優解內的較大值
    }

    size[n][n]=max(size[n-1][n],size[n-1][C[n]-1]+1);//書上總喜歡把最后一項單獨計算.有時候是有問題的，就像0-1背包，雖然節約了時間
}

int Traceback(int C[],int size[][20],int n,int Net[])//構造最優解(從最后一項開始構造)
{
    int j=n,i;
    int m=0;
    for(i=n;i>1;i--)   //1<i<=n
    {
        if(size[i][j]!=size[i-1][j])   //代表第i條入選
        {
            Net[m++]=i;
            j=C[i]-1;    //這里j的目的是為了構造第一條線路是否入選，應為i!=1
        }
    }

    if(j>=C[1])           //入選
        Net[m++]=1;

    return m;
}

int main()
{
    int C[20]={0,8,7,4,2,5,1,9,3,10,6},size[20][20],i,j,n,k;
    int Net[20];

    memset(size,0,sizeof(size));
    memset(Net,0,sizeof(Net));

    MNS(C,10,size);//構造最優解

    printf("最優解矩陣：\n");
    n=10;
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=n;j++)
        {
            printf("%d ",size[i][j]);
        }
        printf("\n");
    }

    k=Traceback(C,size,n,Net);
    
    printf("最優線路：\n");
    for(i=0;i<k;i++)
        printf("%d ",Net[i]);
    printf("\n");


    return 0;
}

 運行結果如下：

     摘要:             工作的時候寫的一個修改記事本的程序段。記錄下代碼如下： #include <windows.h>#include <stdio.h>#include <string.h>#include&...  閱讀全文             雖然說求最大值最小值函數在哪個頭文件下并不是非常重要，但是遇到問題的時候我們很快的找到~~  MSDN上說在algorithm下，但是出錯了，其實這兩個函數需要包含兩個頭文件<windows.h>和<windef.h>文件，其他的還有__min和__max需要包含<stdlib.h>頭文件。。



運行結果如下：

免費餡餅

Time Limit:1000MS  Memory Limit:65536K
Total Submit:615 Accepted:149

Description

都說天上不會掉餡餅，但有一天gameboy正走在回家的小徑上，忽然天上掉下大把大把的餡餅。說來gameboy的人品實在是太好了，這餡餅別處都不掉，就掉落在他身旁的10米范圍內。餡餅如果掉在了地上當然就不能吃了，所以gameboy馬上卸下身上的背包去接。但由于小徑兩側都不能站人，所以他只能在小徑上接。由于gameboy平時老呆在房間里玩游戲，雖然在游戲中是個身手敏捷的高手，但在現實中運動神經特別遲鈍，每秒種只有在移動不超過一米的范圍內接住墜落的餡餅。現在給這條小徑如圖標上坐標：

 

為了使問題簡化，假設在接下來的一段時間里，餡餅都掉落在0-10這11個位置。開始時gameboy站在5這個位置，因此在第一秒，他只能接到4,5,6這三個位置中期中一個位置上的餡餅。問gameboy最多可能接到多少個餡餅？（假設他的背包可以容納無窮多個餡餅）

 

Input

輸入數據有多組。每組數據的第一行為以正整數n(0 < n < 100000)，表示有n個餡餅掉在這條小徑上。在結下來的n行中，每行有兩個整數x,T(0 <= T < 100000),表示在第T秒有一個餡餅掉在x點上。同一秒鐘在同一點上可能掉下多個餡餅。n=0時輸入結束。

Output

每一組輸入數據對應一行輸出。輸出一個整數m，表示gameboy最多可能接到m個餡餅。
提示：本題的輸入數據量比較大，建議用scanf讀入，用cin可能會超時。

Sample Input

6
5 1
4 1
6 1
7 2
7 2
8 3
0

 

Sample Output

4

 

Source

hdu1176

                        這個題目也屬于簡單的動態規劃題目，如果直觀的從深度搜索的方法去做可能會超時，很多時候我們采用數組填表的方式求解，以空間換取時間！！
                        如果這個題目還有個小變化，就是撿餅人一開始站在5號位置，所以如果往我們直接從上往下求，只能求得最后每個點上的最優值，所以我們應該從后往前求，求得第一秒的時候每個點上的最優值，也就是題目要求的解！！
代碼如下：

計算直線的交點數

Time Limit:1000MS  Memory Limit:65536K
Total Submit:260 Accepted:119

Description

平面上有n條直線，且無三線共點，問這些直線能有多少種不同交點數。
比如,如果n=2,則可能的交點數量為0(平行)或者1(不平行)。

Input

輸入數據包含多個測試實例,每個測試實例占一行,每行包含一個正整數n（n <= 20）,n表示直線的數量.

Output

每個測試實例對應一行輸出，從小到大列出所有相交方案，其中每個數為可能的交點數,每行的整數之間用一個空格隔開。

Sample Input

2
3

 

Sample Output

0 1
0 2 3

 

Source

hdu1466

            題目意思很明確，網上有很多的解釋都差不多，我記得從前我做這個題目的時候感到很糾結，主要還是看代碼的時候不容易看懂，現在稍微好一點了，總之一定要自己去畫，這樣才會理解！！
         網上代碼如下（我再解釋一下）：
            其實可以直接這么寫，容易理解一點。。
代碼如下：
         C語言中的time：
         代碼如下：

         數據字節數輸出：
         代碼如下：

         printf輸出格式：
         代碼如下：

去北京看奧運

Time Limit:1000MS  Memory Limit:65536K
Total Submit:398 Accepted:116

Description

2008年將到，王飛同學化了九牛二虎之力搞到了2張2008年奧運會足球賽決賽的門票。真是開心啊！他爸爸準備開車跟他一起去北京看球賽。不過門票費好貴啊，所以他爸爸說了，這個錢要在下學期的生活費里扣（好摳門），不過如果他能讓從杭州去北京的油費最省（油價最近漲的好厲害啊），那么就不扣生活費了。
哈哈，這個就難不倒他了。在ACM里可不是白混的。
很快他算出了汽車從杭州到北京必須要加幾次油，并查出了到北京要經過哪幾個城市，每個城市有哪些加油站以及從某城市各加油站到另一城市各加油站的距離和路況算出了各加油站之間的耗油量。
下面是不是很easy?

 

 

Input

有多個測試案例。第一行先輸入測試案例的數目T。
對于每個測試案例，第一行輸入一個整數n表示將在中途n（0 < n < 40)個城市中加油，后面緊跟著是n個整數代表每個城市有幾個加油站(每個城市加油站不超過10個）。
以下n+1行，每行由3個S_i,E_j,L一組組成的好幾對整數，該行以0結束。表示從前一城市S_i第i個加油站（杭州的話就是家拉）出發到該城市第j個加油站消耗的油量為L升。

Output

對于每個測試，輸出一行，內容為最小總耗油量。

Sample Input

1
2 2 3
1 1 3 1 2 1 0
1 1 2 1 2 7 2 1 8 2 2 9 2 3 4 0
1 1 5 2 1 6 3 1 6 0

 

Sample Output

10

         中文題，這種是最簡單的動態規劃問題了，從左往右折，每次求得各個加油站上最小耗油量！！！

         看代碼的時候發現自己寫的看不懂了。。。。悲劇！！！代碼實現能力仍然是個話題啊！！

代碼如下：

#include<stdio.h>
#include<string.h>
int main()
{
    int num1[50];
    int num2[50];            //暫時存儲中間結果
    int num3[50];            //結果數組
    int t,n,k,s,e,i,g,m,j;
    int l;
    scanf("%d",&t);            //組數
    for(m=0;m<t;m++)
    {
        for(j=0;j<15;j++)    //初始化num3
            num3[j]=0;

        scanf("%d",&n);        //城市個數

        for(i=0;i<n;i++)    //城市加油站個數沒用。。。
            scanf("%d",&k);

        for(i=0;i<n+1;i++)    //n個城市要走n步
        {
            for(j=0;j<15;j++)    //初始化
                num2[j]=1000000;

            for(j=0;j<15;j++)    //初始化
                num1[j]=0;

            while(scanf("%d",&g)!=EOF&&g!=0)//參數判定
            {    
                s=g;
                scanf("%d %d",&e,&l);    
                
                if(num2[e]==1000000)        
                {
                    num1[e]=num3[s]+l;
                    num2[e]=num1[e];
                }

                else if(num3[s]+l<=num2[e])
                {
                    num1[e]=num3[s]+l;
                    num2[e]=num1[e];
                }            

            }

            for(j=0;j<50;j++)            //結果存儲
                num3[j]=num2[j];

        }                

        printf("%d\n",num3[1]);            //輸出結果
    }
    return 0;
}

            學以致用！！！
            隨機數可以用來計算概率，面積等！！
         一、隨機數，模擬拋硬幣正面時間頻率圖。
         代碼如下：

運行結果如下：
 
         二、隨機數，計算∏。基本思想也是運用了概率事件！設有一個半徑為r的圓及其外切四邊形，向該圖形投擲N個點。設落入圓內的點數為K，由于投入的點在正方形上分布均勻，所以落入圓中的概率為∏*R^2/4/R^2，從投點的角度考慮，該概率為K/N，當N足夠大時，我們可以近似的認為二者相等。從而∏=4*K/N。
代碼如下：

當n=500000000時，運行結果如下：
 

printf輸出：http://hi.baidu.com/jiaju111/blog/item/dcd7fd8ba9a7fa1ac9fc7ae2.html

C語言時間日期函數說明：http://www.cnblogs.com/neonlight/archive/2008/08/22/1273942.html                在別人眼里輕而易舉的的事情落在自己身上可能比登天還要難！！
                0-1背包問題：給定n中物品和一個背包。物品i的重量是wi，價值為vi，背包的容量為c。問如何選擇裝入背包中的武平，使得裝入背包中的物品價值最大？
               書上有一行行的算式，證明最優子結構性質和構造遞歸關系。我沒怎么看明白最優子結構，但是我能看懂遞歸關系式！！我記得當時老師叫我們的時候我自己想了好幾天才想明白這個遞歸式，但是始終覺得有點虛，借此我再寫一下！
               設數組m(i,j)代表背包容量為j，可選物品為i，i+1，..n時的最優解（這里的最優解指的是選擇方案，并非正真的最優值），顯然m(1,c)是0-1背包問題的解（這里是書上的錯誤，應該是m[1]中的最大值！！我后來才發現的。。）。這種定義雖然比較拗口，但是還是可以接受的，其實我們也可以這么定義m[i][j],代表背包容量為j，當前選擇物品為a[i]時的最優解，顯然m數組中第n行的最大值是0-1背包問題的解！！

第一種定義的遞歸式如下：
                              0                  1
   m[i][j]=max{m[i+1][j],m[i+1][j-wi]+vi}  j>=wi;    m[i][j]=m(i+1,j)   0<=j<wi

第二種定義的遞歸式如下：
                              0                  1
   m[i][j]=max{m[i-1][j],m[i-1][j-wi]+vi}    j>=wi;    m[i][j]=m(i-1,j)   0<=j<wi

代碼如下：

運行結果如下：

    
               第二種遞歸思路下的代碼和運行過程我就不寫，就初始化和遞歸次序不同！！
               我一個同學經常跟我說，以后自己有孩子，一個賺了1000給我花100，一個賺了10000給我花200，我還是跟著賺1000的吧！！其實問題不在別人，而在自己，努力就成！！！我受益匪淺。。。