/*小明開了一家糖果店。他別出心裁：把水果糖包成4顆一包和7顆一包的兩種。糖果不能拆包賣。
小朋友來買糖的時候，他就用這兩種包裝來組合。當然有些糖果數目是無法組合出來的，比如要買 10 顆糖。
你可以用計算機測試一下，在這種包裝情況下，最大不能買到的數量是17。大於17的任何數字都可以用4和7組合出來。
本題的要求就是在已知兩個包裝的數量時，求最大不能組合出的數字。
輸入：
兩個正整數，表示每種包裝中糖的顆數(都不多於1000)
要求輸出：
一個正整數，表示最大不能買到的糖數
例如：
用戶輸入：
4 7
程序應該輸出：
17
再例如：
用戶輸入：
3 5
程序應該輸出：
7*/
方法一:
[cpp]
#include"stdio.h"
#include"stdlib.h"
#include"time.h"
#define max 100000000
int main()
{int m,n;
long int start,finish;
scanf("%d %d",&m,&n);
start=clock();
long int *p;
p=(long *)malloc(sizeof(long)*max);//開辟空間,建立一張0,1表
p[0]=1;//初始化
for(long int i=1;i<max;i++)
{p[i]=0;//初始化
if(i>=m&&p[i-m]) p[i]=1;
else
if(i>=n&&p[i-n]) p[i]=1;
}
long int kk=0;
for(long int i=0;i<max;i++)
{if(i>kk&&!p[i])
kk=i;
}
printf("%ld",kk);
finish=clock();
printf("\nall time is: %lfs",(finish-start)/1000.0);
printf("\n");
system("pause");
}
#include"stdio.h"
#include"stdlib.h"
#include"time.h"
#define max 100000000
int main()
{int m,n;
long int start,finish;
scanf("%d %d",&m,&n);
start=clock();
long int *p;
p=(long *)malloc(sizeof(long)*max);//開辟空間,建立一張0,1表
p[0]=1;//初始化
for(long int i=1;i<max;i++)
{p[i]=0;//初始化
if(i>=m&&p[i-m]) p[i]=1;
else
if(i>=n&&p[i-n]) p[i]=1;
}
long int kk=0;
for(long int i=0;i<max;i++)
{if(i>kk&&!p[i])
kk=i;
}
printf("%ld",kk);
finish=clock();
printf("\nall time is: %lfs",(finish-start)/1000.0);
printf("\n");
system("pause");
}//少量優化,當這個數字更加的大的時候如果出現了n個連續的p[i]==1的情況,那麼後面的所有數字都不用再判斷,如此優化,n<m
方法二:
[cpp]
#include"stdio.h"
#include"stdlib.h"
#include"time.h"
#define max 100000000
int main()
{int m,n,temp;
long int start,finish;
scanf("%d %d",&m,&n);
start=clock();
long int *p;
p=(long *)malloc(sizeof(long)*max);//開辟空間,建立一張0,1表
p[0]=1;//初始化
if(m<n)
{temp=m; m=n ;n=temp;}//保證n<m
temp=0;//初始化
for(long int i=1;i<max;i++)
{p[i]=0;//初始化
if(i>=m&&p[i-m]) p[i]=1;
else
if(i>=n&&p[i-n]) p[i]=1;
if(p[i]) temp++; else temp=0;
if(temp==n) {printf("%ld",i-n); break; }
}
/*long int kk=0;
for(long int i=0;i<max;i++)
{if(i>kk&&!p[i])
kk=i;
}
printf("%ld",kk);*/
finish=clock();
printf("\nall time is: %lfs",(finish-start)/1000.0);
printf("\n");
system("pause");
}
#include"stdio.h"
#include"stdlib.h"
#include"time.h"
#define max 100000000
int main()
{int m,n,temp;
long int start,finish;
scanf("%d %d",&m,&n);
start=clock();
long int *p;
p=(long *)malloc(sizeof(long)*max);//開辟空間,建立一張0,1表
p[0]=1;//初始化
if(m<n)
{temp=m; m=n ;n=temp;}//保證n<m
temp=0;//初始化
for(long int i=1;i<max;i++)
{p[i]=0;//初始化
if(i>=m&&p[i-m]) p[i]=1;
else
if(i>=n&&p[i-n]) p[i]=1;
if(p[i]) temp++; else temp=0;
if(temp==n) {printf("%ld",i-n); break; }
}
/*long int kk=0;
for(long int i=0;i<max;i++)
{if(i>kk&&!p[i])
kk=i;
}
printf("%ld",kk);*/
finish=clock();
printf("\nall time is: %lfs",(finish-start)/1000.0);
printf("\n");
system("pause");
}
