C語言程式設計100例之（60）：集合

例60   集合

問題描述

一個集合S中有N個整數，找出其中值最大的元素D，滿足條件A+B+C=D，并且A、B、C、D這四個不同的整數都屬于集合S，

輸入

輸入包括多組測驗用例，每組測驗用例由一個整數n（1<=n<=1000），表示S中的元素個數，后跟S中的n個元素，每行一個，S的每個元素都是一個介于-536870912和+536870911（含）之間的不同整數，輸入的最后一行包含0，

輸出

對于每組測驗用例，輸出一行，為求得的最大值D，或一行包含“no solution”，

輸入樣例

5

2

3

5

7

12

5

2

16

64

256

1024

0

輸出樣例

12

no solution

        （1）編程思路，

        采用列舉法，但不能用4重回圈直接列舉，時間復雜度太高，

        先將集合S中的n個元素從小到大進行排列，然后最外層回圈從大到小列舉元素D的值（即S[n-1]~S[0]，i=n-1~0），第1層內回圈中從小到大列舉元素A的值（即S[0]~S[n-1]，j=0~n-1），再在第1層內回圈中這樣列舉B和C的值：

        1）置初始的B為S[j+1]，記下標head=j+1，置初始的C值為S[n-1]，記下標tail=n-1；

        2）若head與tail相等，則對B和C的列舉結束，則當前的A值（s[j]）不可能是滿足條件的解，進行A的下一個列舉；

        3）求A、B、C的和，即sum= s[j]+s[head]+s[tail]；

        4）若sum=s[i]，且下標i與j、head、tail均不相同，則找到最大的D，結束列舉程序，輸出D的值；

        5）若sum>s[i]，則減小C的值，使sum可以減小到與D可能相等，即tail減1，轉3）；

        6）若sum<s[i]，則增大B的值，使sum可以增大到與D可能相等，即head加1，轉3）；

        若所有列舉結束，沒有求得最大值D，則輸出無解資訊“no solution”，

（2）源程式，

#include <stdio.h>

int main()

{

    int n;

    int s[1010];

    while(scanf("%d",&n)&& n!=0)

    {

        int flag=0;

        int i,j,t;

        for (i=0; i<n; i++)

            scanf("%d",&s[i]);

        for (i=0;i<n-1;i++)

           for (j=0;j<n-1-i;j++)

              if (s[j]>s[j+1])

              {

                 t=s[j]; s[j]=s[j+1]; s[j+1]=t;

              }

        int ans;

        for (i=n-1; i>=0 && flag==0; i--)

        {

            for (j=0; j<n-1 && flag==0; j++)

            {

                int head=j+1,tail=n-1;

                while (head<tail)

                {

                    int sum=s[j]+s[head]+s[tail];

                    if (sum==s[i])

                    {

                        if (i==j||i==head||i==tail) break;

                        ans=sum;

                        flag=1;

                        break;

                    }

                    else if (sum>s[i]) tail--;

                    else head++;

                }

             }

        }

        if (flag==1)

            printf("%d\n",ans);

        else

            printf("no solution\n");

    }

    return 0;

}

習題60

60-1  等引數列

題目描述

小紅特別喜歡等引數列，尤其是公差為1且全為正整數的等引數列，

顯然，對于每一個數s，都能找到一個對應的公差為1且全為正整數的等引數列各項之和為 s，這時，小紅想知道，滿足這樣條件的等引數列，最小的首項是多少，

由于小紅的數學非常差，尤其是因式分解，所以請你告訴她結果，

輸入格式

輸入僅包含一行一個整數s (1≤s≤1012)，

輸出格式

輸出兩個正整數，分別表示這個等引數列的首項和末項，請注意輸出最小的首項，

輸入樣例

9

輸出樣例

2 4

        （1）編程思路

        設等引數列的首項為a1，項數為n，由等引數列求和公式易得：

        因為a1為正整數，因此2S=(2*a1+n-1)*n >(n-1)*n >(n-1)*(n-1)，所以n-1一定小于sqrt(2*s)，即n一定小于sqrt(2*s)+1，這樣可以對項數n從大到小進行列舉，找到第1個滿足使a1為正整數的n就可以，因為從大道小進行列舉，所以找到的第1個n值肯定滿足使a1最小，a1+n-1就是末項，

       （2）源程式，

#include <stdio.h>

#include <math.h>

int main ()

{

    long long s;

    scanf("%lld",&s);

    long long num=2*s;

    long long maxx=sqrt(num)+1;

    long long i;

    long long n;

    for (i=maxx;i>=1;i--)   // 列舉項數n

    {

        if ((num-i*i+i)%(2*i)==0 && (num-i*i+i)>0)

        {

            n=i;

            break;

        }

    }

    long long a=(num-n*n+n)/(2*n);

   printf("%lld %lld\n",a,a+n-1);

   return 0;

}

60-2  臨時征用

問題描述

在一條長馬路上設定了P（1<=P<=1000）根等距標桿，相鄰兩根標桿間搭建了一個簡易板房，板房編號從1~P-1，N（1<=N<=1000）個工人各自入住某個板房，一個板房中可以入住多名工人，現由于某種需要，需要臨時征用一片連續的板房，被征用的板房中若入住有工人，則需要重新安置，

請確定可被征用的連續板房的最大數量，征用后被重新安置的個人不超過C（0<=C<=1000）名，

輸入

第1行：三個整數N、P和C，

第2~N+1行：每行包含一個整數X，范圍為1~P-1，表示工人入住的板房號，

輸出

一個整數，可被征用的連續板房的最大數量，

輸入樣例

2 6 1

2

3

輸出樣例

3

         （1）編程思路，

        定義陣列int cnt[1005]={0}，其中cnt[i]表示入住編號為i的板房中工人的人數，

        對區間[i,j]進行列舉（1<=i<p，i<=j<p），每次列舉，統計編號在區間[i,j]中板房里入住的人數sum，若sum<=C，則可征用的連續板房數量為j+1-i，記錄所有j+1-i中的最大值即可，

       （2）源程式，

#include <stdio.h>

int main()

{

    int n,p,c;

    scanf("%d%d%d",&n,&p,&c);

    int cnt[1005]={0},ans=0;

    int i,j;

    for (i=1;i<=n;i++)

    {

        int x;

        scanf("%d",&x);

        cnt[x]++;

    }

    for (i=1;i<p;i++)

    {

        int sum=0;

        for (j=i; j<p && sum+cnt[j]<=c;j++)

            sum+=cnt[j];

        if (ans<j-i) ans=j-i;

    }

    printf("%d",ans);

    return 0;

}

60-3  找零錢

問題描述

商店有面值為25分、10分、5分、1分的硬幣，給出各硬幣的數量和要找給顧客的錢數，問怎么使找給顧客的總的硬幣數最少，

輸入

輸入由一行或多行組成，每行的形式如下：

Q D N P C

式中，Q是25分硬幣數，D是10分硬幣數，N是五分硬幣數，P是1分硬幣數，C是要找給客戶的錢數（以分為單位），

輸入最后由一行5個零表示結束，

輸出

對于每一行輸入資料，您的程式應輸出：

Dispense # quarters, # dimes, # nickels, and # pennies.

若無法準確找零，則輸出 Cannot dispense the desired amount.

輸入樣例

5 9 9 9 37

0 9 9 9 37

10 10 10 0 37

1 3 0 10 30

1 3 6 10 30

0 0 0 0 0

輸出樣例

Dispense 1 quarters, 1 dimes, 0 nickels, and 2 pennies.

Dispense 0 quarters, 3 dimes, 1 nickels, and 2 pennies.

Cannot dispense the desired amount.

Dispense 0 quarters, 3 dimes, 0 nickels, and 0 pennies.

Dispense 1 quarters, 0 dimes, 1 nickels, and 0 pennies.

         （1）編程思路，

        直接用i，j，k三個變數對25分、10分和5分的硬幣個數進行窮舉，窮舉范圍為

        0≤i≤Q ， 0≤j≤D，0≤k≤N

        對窮舉的每種情況，計算1分硬幣的個數 r=C-( i*25+j*10+k*5)，若0≤r≤P，則當前i,j,k,r值是一種可行的找零方案，方案數cnt++，若找零數量i+j+k+r最小，用陣列ans[4]保存這四個值，

       （2）源程式1，

#include <stdio.h>

int main()

{

    int Q,D,N,P,C;

    while(scanf("%d%d%d%d%d",&Q,&D,&N,&P,&C)&&(Q||D||N||P||C))

    {

          int i,j,k,cnt=0;

          int minn=Q+D+N+P+1;

          int ans[4]={0};

          for (i=0;i<=Q;i++)

           for (j=0;j<=D;j++)

               for (k=0;k<=N;k++)

             {

            int r=C-(i*25+j*10+k*5);

            if (r>=0 && r<=P)

            {

                int n=i+j+k+r;

                            if (n<minn)

                {

                    ans[0]=i;  ans[1]=j;

                    ans[2]=k;  ans[3]=r;

                    cnt++;

                    minn=n;

                }

            }

         }

          if (cnt==0)

                printf("Cannot dispense the desired amount.\n");

          else

                printf("Dispense %d quarters, %d dimes, %d nickels, and %d pennies.\n",ans[0],ans[1],ans[2],ans[3]);

       }

       return 0;

}

        也可以采用深度優先搜索求解，撰寫如下的源程式2，

        （3）源程式2，

#include <stdio.h>

int cnt=0,minn=0;

int c[4]={25,10,5,1};

int w[5],ans[5],num[5];

void dfs(int x,int tot)

{

     int i,j,n;

     if (x>3) return;

     for (i=0; i<=w[x]; i ++)

     {

        int temp = tot-i*c[x];

        if (temp<0) break;

        else if (temp==0)

        {

            cnt++;

            for (j=n=0; j<x; j++)

                n += num[j];

            if (n+i<minn)

            {

                for (j=0; j<x; j++)

                {

                    ans[j]=num[j];

                }

                ans[x] = i;

                for (j=x+1; j<4; j++)

                {

                    ans[j]=0;

                }

                minn=n+i;

            }

            break;

        }

        else

        {

            num[x] = i;

            dfs(x+1, temp);

        }

    }

}

int main()

{

    int cents;

    while(scanf("%d%d%d%d%d",&w[0],&w[1],&w[2],&w[3],&cents)&&(w[0]||w[1]||w[2]||w[3]||cents))

    {

              minn=w[0]+w[1]+w[2]+w[3]+1;

              cnt=0;

              dfs(0,cents);

              if (cnt==0)

                     printf("Cannot dispense the desired amount.\n");

              else

                     printf("Dispense %d quarters, %d dimes, %d nickels, and %d pennies.\n",ans[0],ans[1],ans[2],ans[3]);

       }

       return 0;

}

標籤：其他

上一篇：java 圖片水印處理類

下一篇：Go代碼規范梳理