打靶有关问题，求最快算法，100分
打靶问题，求最快算法，100分
战士们做了一个靶子，靶子分五格，中心是39环，从左起顺时针是23、17、24 、16。
战士小李射了若干枪，每一次都击中靶子，并且正好是100环。问他打了几枪？每枪
多小环？
int del[]={17,23,16,24,39};
int delOut[]={0,0,0,0,0};
void reset(int n)
{
for(;n <sizeof(delOut)/sizeof(delOut[0]);n++)
delOut[n]=0;
}
void out_put()
{
for(int i=0;i <sizeof(delOut)/sizeof(delOut[0]);i++)
printf( "%10d ",delOut[i]);
printf( "\n ");
}
void sort()//del 从大到小
{
for(int i=0;i <sizeof(del)/sizeof(del[0]);i++)
for(int j=i+1;j <sizeof(del)/sizeof(del[0]);j++)
if(del[j]> del[i]){
int t=del[j];
del[j]=del[i];
del[i]=t;
}
}
void __fastcall fun(int total,int n)
{
if(n> sizeof(del)/sizeof(del[0])-1)
return;
reset(n);
if(n==sizeof(del)/sizeof(del[0])-1){
if(total %del[n]==0){
delOut[n]=total/del[n];
// out_put(); // 显示很慢 要的时候 total =1000,近8s秒，不要17ms
}
}else{
for(int i=0;i <total/del[n];i++){
delOut[n]=i;
fun(total-del[n]*i,n+1);
}
}
}
int main(int argc, char* argv[])
{
long start=GetTickCount();
sort();
fun(1000,0);
long end=GetTickCount();
printf( "time %d ",end-start);
}
把100 一环改成1000 试一下你的算法速度
------解决方案--------------------
我把原先的程序改成函数形式，看看代码就知道其效率。
循环次数少（由函数关系控制范围），循环中只有 if( !(s4%c5) ) 运算。
#include <stdio.h>
void hit5(int s, int c1, int c2, int c3, int c4, int c5)
{
int x1, x2, x3, x4;
int s1, s2, s3, s4;
printf( " 中%i环数, 中%i环数,中%i环数,中%i环数,中%i环数\n ", c1, c2, c3, c4, c5);
for(s1 = s, x1 = 0; s1 > = 0; x1++, s1-=c1) // 加中c1环
for(s2 = s1, x2 = 0; s2 > =0; x2++, s2-=c2) // 加中c2环
for(s3 = s2, x3 = 0; s3 > =0; x3++, s3-=c3) // 加中c3环
for(s4 = s3, x4 = 0; s4 > =0; x4++, s4-=c4)//加中c4环
if( !(s4%c5) ) // 判断是否中c5环
printf( " %8d, %8d, %8d, %8d, %8d\n ", x1, x2, x3, x4, s4/16);
}
void main()
{
hit5(1000， 39， 24， 23， 17， 16);
}
------解决方案--------------------
思路：
某数N的解集可以由多个n+c组成，其中n是5环数中的一个，c是一个已取得解的数。
因此某数N的解集最多为5个。c的解集也为5个，同时c也由n+c1组成，以此类推。
例如：
50可以由17+33组成，那么就在50地解集中填上17和33，而33的解集也由此类推。
因此，问题可以简化成1000x5的2重循环，并且循环内部都是简单查表运算。
缺点是需要大概40k的内存来存储表，另外输出的结果排版比较抽象，也没有剔除重复数据。
#include <stdio.h>
#include <stdlib.h>
#define MAX_SCORES 5
#define TARGET_COMBINE 1000
typedef struct _tagCombine {
int n; // score, 0 for invalid
int c; // index of combine, 0 for invalid
} COMBINE;
COMBINE recs[MAX_SCORES][TARGET_COMBINE+1];
const int scores[MAX_SCORES] = { 39, 23, 17, 24, 16 };
void dumpcomb(int index, int final)
{
int i;
for ( i = 0; i < MAX_SCORES; ++i ) {
if ( recs[i][index].n == 0 ) break;
if ( !final && i != 0 ) printf( "| ");
if ( recs[i][index].c == 0 ) {
// leaf
printf( "%d ", recs[i][index].n);
} else {
// combine
战士们做了一个靶子，靶子分五格，中心是39环，从左起顺时针是23、17、24 、16。
战士小李射了若干枪，每一次都击中靶子，并且正好是100环。问他打了几枪？每枪
多小环？
int del[]={17,23,16,24,39};
int delOut[]={0,0,0,0,0};
void reset(int n)
{
for(;n <sizeof(delOut)/sizeof(delOut[0]);n++)
delOut[n]=0;
}
void out_put()
{
for(int i=0;i <sizeof(delOut)/sizeof(delOut[0]);i++)
printf( "%10d ",delOut[i]);
printf( "\n ");
}
void sort()//del 从大到小
{
for(int i=0;i <sizeof(del)/sizeof(del[0]);i++)
for(int j=i+1;j <sizeof(del)/sizeof(del[0]);j++)
if(del[j]> del[i]){
int t=del[j];
del[j]=del[i];
del[i]=t;
}
}
void __fastcall fun(int total,int n)
{
if(n> sizeof(del)/sizeof(del[0])-1)
return;
reset(n);
if(n==sizeof(del)/sizeof(del[0])-1){
if(total %del[n]==0){
delOut[n]=total/del[n];
// out_put(); // 显示很慢 要的时候 total =1000,近8s秒，不要17ms
}
}else{
for(int i=0;i <total/del[n];i++){
delOut[n]=i;
fun(total-del[n]*i,n+1);
}
}
}
int main(int argc, char* argv[])
{
long start=GetTickCount();
sort();
fun(1000,0);
long end=GetTickCount();
printf( "time %d ",end-start);
}
把100 一环改成1000 试一下你的算法速度
------解决方案--------------------
我把原先的程序改成函数形式，看看代码就知道其效率。
循环次数少（由函数关系控制范围），循环中只有 if( !(s4%c5) ) 运算。
#include <stdio.h>
void hit5(int s, int c1, int c2, int c3, int c4, int c5)
{
int x1, x2, x3, x4;
int s1, s2, s3, s4;
printf( " 中%i环数, 中%i环数,中%i环数,中%i环数,中%i环数\n ", c1, c2, c3, c4, c5);
for(s1 = s, x1 = 0; s1 > = 0; x1++, s1-=c1) // 加中c1环
for(s2 = s1, x2 = 0; s2 > =0; x2++, s2-=c2) // 加中c2环
for(s3 = s2, x3 = 0; s3 > =0; x3++, s3-=c3) // 加中c3环
for(s4 = s3, x4 = 0; s4 > =0; x4++, s4-=c4)//加中c4环
if( !(s4%c5) ) // 判断是否中c5环
printf( " %8d, %8d, %8d, %8d, %8d\n ", x1, x2, x3, x4, s4/16);
}
void main()
{
hit5(1000， 39， 24， 23， 17， 16);
}
------解决方案--------------------
思路：
某数N的解集可以由多个n+c组成，其中n是5环数中的一个，c是一个已取得解的数。
因此某数N的解集最多为5个。c的解集也为5个，同时c也由n+c1组成，以此类推。
例如：
50可以由17+33组成，那么就在50地解集中填上17和33，而33的解集也由此类推。
因此，问题可以简化成1000x5的2重循环，并且循环内部都是简单查表运算。
缺点是需要大概40k的内存来存储表，另外输出的结果排版比较抽象，也没有剔除重复数据。
#include <stdio.h>
#include <stdlib.h>
#define MAX_SCORES 5
#define TARGET_COMBINE 1000
typedef struct _tagCombine {
int n; // score, 0 for invalid
int c; // index of combine, 0 for invalid
} COMBINE;
COMBINE recs[MAX_SCORES][TARGET_COMBINE+1];
const int scores[MAX_SCORES] = { 39, 23, 17, 24, 16 };
void dumpcomb(int index, int final)
{
int i;
for ( i = 0; i < MAX_SCORES; ++i ) {
if ( recs[i][index].n == 0 ) break;
if ( !final && i != 0 ) printf( "| ");
if ( recs[i][index].c == 0 ) {
// leaf
printf( "%d ", recs[i][index].n);
} else {
// combine