Ctrl C+V
作法:DFS搜尋所有可能
想法:複製完,一定是接貼上,及早達到星星的數目,之後一大於最小次數就退回
2009/7/14更新 由於zhouyuchen寫的超快,以至於產生新的做法
不過感謝zhouyuchen提供想法(雖然看不懂)
第2程式碼為DFS+倍數判斷(速度為第1程式碼的40倍)
/********************************************************/
#include<stdio.h>
#include<stdlib.h>
char way[2000][10000]={0};
int n,min,top;
int temp[10000]={0};
int num[25]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
void DFS(int sum,int many,int ctrlC,int ctrlV)
{
if(sum==n&&min>=many)
{
int a;
if(min==many)
{
top++;
for(a=0;a<=many;a++) way[top][a]=temp[a];
}
else
{
top=0;
for(a=0;a<=many;a++) way[top][a]=temp[a];
}
min=many;
}
if(many>=min||sum>n) return;
if(ctrlC==1)/*複製過的話 一定是接貼上*/
{
temp[many+1]=2;
DFS(sum+ctrlV,many+1,0,ctrlV);
}
else
{
temp[many+1]=1;
DFS(sum,many+1,1,sum);
temp[many+1]=2;
DFS(sum+ctrlV,many+1,0,ctrlV);
}
}
main()
{
int a,b;
while(scanf("%d",&n)==1)
{
int find=0;
for(a=0;a<25&&num[a]<n;a++)
if(n%num[a]==0) {find=1;break;}
if(find==1)
{
min=2147483647;
DFS(1,1,1,1);
printf("min : %d\n",min);
printf("way : %d\n",top+1);
for(b=0;b<=top;b++)
{
printf("Ctrl C + ");
for(a=2;a<min;a++)
if(way[b][a]==1) printf("C + ");
else if(way[b][a]==2) printf("V + ");
if(way[b][a]==1) printf("C");
else if(way[b][a]==2) printf("V");
printf("\n");
}
}
else
{
printf("min : %d\n",n);
printf("way : %d\n",1);
printf("Ctrl C + ");
for(a=2;a<n;a++)
printf("V + ");
printf("V");
printf("\n");
}
}
return 0;
}
/*********************************************************/
#include<stdio.h>
#include<stdlib.h>
char way[2000][10000]={0};
int n,min,top;
int temp[10000]={0};
void DFS(int sum,int many,int ctrlC,int ctrlV)
{
if(sum==n&&min>=many)
{
int a;
if(min==many)
{
top++;
for(a=0;a<=many;a++) way[top][a]=temp[a];
}
else
{
top=0;
for(a=0;a<=many;a++) way[top][a]=temp[a];
}
min=many;
}
if(many>=min||sum>=n) return;
if(ctrlC==1)/*複製過的話 一定是接貼上*/
{
temp[many+1]=2;
DFS(sum+ctrlV,many+1,0,ctrlV);
}
else
{
if(n%sum==0)
{
temp[many+1]=1;
DFS(sum,many+1,1,sum);
}
temp[many+1]=2;
DFS(sum+ctrlV,many+1,0,ctrlV);
}
}
main()
{
int a,b;
while(scanf("%d",&n)==1)
{
min=2147483647;
DFS(1,1,1,1);
printf("min : %d\n",min);
printf("way : %d\n",top+1);
for(b=0;b<=top;b++)
{
printf("Ctrl C + ");
for(a=2;a<min;a++)
if(way[b][a]==1) printf("C + ");
else if(way[b][a]==2) printf("V + ");
if(way[b][a]==1) printf("C");
else if(way[b][a]==2) printf("V");
printf("\n");
}
}
return 0;
}
400多ms真快 min=n 應該也可以。
為什麼質數表只有一點點?
題目的提示讓我好無言......
我用 backtracking ,想法一樣,判斷的東西也差不多,是 backtracking 會比 DFS 慢?
而且接貼上之後接複製 應該能盡快到達剛好的星星數目
之後把最大的次數降低 將可能一直砍
質數表...10000的根號 是100以內的質數去除就夠了...
其實我也不曉得`XD
修改之後39X ms了 2009-06-02 23:06:41