通过多日的深入研究,终于做成了我的变态比赛规则的最终版!^_^ 其实之前那个C写的版本已经是算法的最终版了.但是想想程序的长度还是有点短了~~老师要求要有复杂性.本来是说要用C\C++做图形界面了(是图形界面,非Visual).但是想想这样是不是太麻烦了,上个学期已经体会过图形界面的制作复杂度了~~(就要写上一个汉字就要用点阵画半天~).终于通过不懈的努力摸清了VC写的dll如何用VB来调用了~~这样就可以VB与C混合编程了.
在VC中用C写成函数封装到dll中只需要添加一个.def文件来定义输出函数名.这样做好dll后在VB中就如同调用API一样来调用就可以了.这种方法适合小型规模的程序,十分方便^_^!!
然后依托VB强大而又方便的Window就可以做出一个花里胡哨的shell了.呵呵,为了加上一点难度,我就使用了VB中所有能使用的图形化编程方法(几乎了^_^!!).添加了FLASH来作为判断所输数据是否满足条件.添加图片装饰窗口.添加一个media player来展示视频(不管效率如何了~~)^_^!!一个呼哨的shell就做好了管他效果如何~~! 当然shell给dll提供了良好的数据过滤功能.
这就是这次课程设计的最终版了.还有最后一张logo拜托了一个学设计的同学来帮忙.要做就做绝对的专业的!^_^~~
2007年3月26日星期一
变态比赛规则的优化
知觉告诉我,我的程序的时间复杂度好像已经很小了(具体是多少啊?我不会算~~).但是看到循环里边那个sqrt函数就不爽!到论坛里求来一个牛牛牛的算法:牛顿迭代法~~名字多牛啊.^_^!!据说这个是在雷神之锤3里边用到的快速求平方根倒数的方法!恩~很牛!经过优化的算法如下: #include <stdio.h>
#include <stdlib.h>
#include <math.h>
float InvSqrt (float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f3759df - (i >> 1); // 计算第一个近似根
x = *(float*)&i;
x = x*(1.5f - xhalf*x*x); // 牛顿迭代法
return x;
}
int Game(int N,long K)
{
long max,LE;
int p,LP;
if( N<=0 ‖ N>500 ‖ K<0 ‖ K>N*(N-1)/2 )
return 0;
if( K==0 ‖ K==N-1)
return 1;
if( N==1 ‖ K<N-1 )
return 0;
max=N*(N-1)/2;
while (1)
{
p=(int)(1.0/ InvSqrt((max-K)*2));
LP=N-p;
if (LP<0) return 0;
if (p==1 && LP>=1) return 1;
LE=max-p*(p-1)/2;
if (LE==K) return 1;
if (LE<K) return 0;
max=LE;
N=LP;
}
}
int main()
{
long K;
int N,Result;
printf("Please input N,K:");
scanf("%d,%d",&N,&K);
Result=Game(N,K);
if (Result) printf("YES");
else printf("NO");
return 1;
}
#include <stdlib.h>
#include <math.h>
float InvSqrt (float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f3759df - (i >> 1); // 计算第一个近似根
x = *(float*)&i;
x = x*(1.5f - xhalf*x*x); // 牛顿迭代法
return x;
}
int Game(int N,long K)
{
long max,LE;
int p,LP;
if( N<=0 ‖ N>500 ‖ K<0 ‖ K>N*(N-1)/2 )
return 0;
if( K==0 ‖ K==N-1)
return 1;
if( N==1 ‖ K<N-1 )
return 0;
max=N*(N-1)/2;
while (1)
{
p=(int)(1.0/ InvSqrt((max-K)*2));
LP=N-p;
if (LP<0) return 0;
if (p==1 && LP>=1) return 1;
LE=max-p*(p-1)/2;
if (LE==K) return 1;
if (LE<K) return 0;
max=LE;
N=LP;
}
}
int main()
{
long K;
int N,Result;
printf("Please input N,K:");
scanf("%d,%d",&N,&K);
Result=Game(N,K);
if (Result) printf("YES");
else printf("NO");
return 1;
}
2007年3月20日星期二
变态比赛规则之初步程序
考虑了几天了,受到上一个高人算法的启发我想到了这样一个算法:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int Game(int N,long K)
{
long max,LE;
int p,LP;
if( N<=0 ‖ N>500 ‖ K<0 ‖ K>N*(N-1)/2 )
return 0;
if( K==0 ‖ K==N-1)
return 1;
if( N==1 ‖ K<N-1 )
return 0;
max=N*(N-1)/2;
while (1)
{
p=(int) sqrt((max-K)*2);
LP=N-p;
if (LP<0) return 0;
if (p==1 && LP>=2) return 1;
LE=max-p*(p-1)/2;
if (LE==K) return 1;
if (LE<K) return 0;
max=LE;
N=LP;
}
}
int main()
{
long K;
int N,Result;
printf("Please input N,K:");
scanf("%d,%d",&N,&K);
Result=Game(N,K);
if (Result) printf("YES");
else printf("NO");
return 1;
}
其算法原理还是基于前两天算法的研究.这个算法纯粹的使用循环而没有使用递归,但是算法复杂度我现在还不得而知(怎么算得啊?忘记了 呵呵~~).另外也不知道算法的正确性是否成立(没有测试数据),仅仅是我感觉上可行.呵呵 再研究~~.另外这个Beta还有可以改进之处.慢慢来吧~~
2007年3月17日星期六
N天以来关于变态比赛的研究~(效率有点慢)
哈哈 经过N天不懈的努力(好像都是玩了~~)终于对这个[变态比赛规则]程序算法有了一定的心得!!~~首先,介绍一下在网上搜到的高人的算法(听说这个题目的算法还不少,但是除了"暴力"递归的我认为在众多的程序中,这个写的比较好.复杂度要比光递归小了好多)
#include
int main(int argc, char *argv[])
{
int n, k;
/*if( argc!=3 )
{
printf("use: %s n k", argv[0]);
return -1;
}
n = atoi(argv[1]);
k = atoi(argv[2]);*/
scanf("%d %d",&n,&k); //input two numbers
if(foo(n, k)>0)
printf("YES\n");
else
printf("NO\n");
return 0;
}
int maxT(int n, int m)
{
if( n<=0 n>500 m<=0 ) return -1; if( m==1 ) return n*(n-1)/2; if( m>=n n==1 )
return 0;
return m*(n-m)+(n-m)*(n-m-1)/2;
}
int minT(int n, int m)
{
if( n<=0 n>500 m<=0 ) return -1; if( m==1 ) return n*(n-1)/2; if( m>=n n==1 )
return 0;
return m*(n-m)+minT(n-m, m);
}
int foo(int n, int k)
{
int max, min;
int m;
if( n<=0 n>500 k<0>n*(n-1)/2 )
return -1;
if( k==0 k==n-1)
return 1;
if( n==1 k0; m-- )
{
max = maxT(n, m);
min = minT(n, m);
if( k<=max &&amp; k>=min )
{
if( foo(n-m, k-m*(n-m))>0 )
return 1;
}
}
return -1;
}
然后,再介绍一下我这几天的心得了.我就是在读这段程序时(呵呵,至今我还没有完全搞明白段代码是个什么意思~~ 那位高手来给点拨一下啊.谢谢!),基本上看懂一点,但是突然受到这段代码的启发,想到了一个算法.首先,我一开始是摸不着头脑,只是明白了按规则最多应该有N*(N-1)/2场比赛[每组一个人],最少应该有N-1场比赛[一组一个人,其他人一组].或者0场比赛[所有人一组].后来换个角度来考虑,觉得不应该从有K场比赛,如何分这N个人来考虑.应该考虑一下有N个人,如何分组才能有这K场比赛.另外,也不应该把所有人分在一组,然后分开一个,然后再一个...这样反倒没有规律了.后来想到如果一开始是每一个人一组,然后没人之间都有比赛这样就是一个完全无向图.而合并一组就是把组内的边除去.也就是m个人分为一组的话,就从N阶完全无向图中除去一个m阶完全无向图.
就这样一直合并直到能得到K条边为止,或者只能得到一个小于K的边数.至于具体的算法我还没写出来^_^!! 同时也不知道这个算法是否可行.拭目以待了^_^!!
#include
int main(int argc, char *argv[])
{
int n, k;
/*if( argc!=3 )
{
printf("use: %s n k", argv[0]);
return -1;
}
n = atoi(argv[1]);
k = atoi(argv[2]);*/
scanf("%d %d",&n,&k); //input two numbers
if(foo(n, k)>0)
printf("YES\n");
else
printf("NO\n");
return 0;
}
int maxT(int n, int m)
{
if( n<=0 n>500 m<=0 ) return -1; if( m==1 ) return n*(n-1)/2; if( m>=n n==1 )
return 0;
return m*(n-m)+(n-m)*(n-m-1)/2;
}
int minT(int n, int m)
{
if( n<=0 n>500 m<=0 ) return -1; if( m==1 ) return n*(n-1)/2; if( m>=n n==1 )
return 0;
return m*(n-m)+minT(n-m, m);
}
int foo(int n, int k)
{
int max, min;
int m;
if( n<=0 n>500 k<0>n*(n-1)/2 )
return -1;
if( k==0 k==n-1)
return 1;
if( n==1 k
{
max = maxT(n, m);
min = minT(n, m);
if( k<=max &&amp; k>=min )
{
if( foo(n-m, k-m*(n-m))>0 )
return 1;
}
}
return -1;
}
然后,再介绍一下我这几天的心得了.我就是在读这段程序时(呵呵,至今我还没有完全搞明白段代码是个什么意思~~ 那位高手来给点拨一下啊.谢谢!),基本上看懂一点,但是突然受到这段代码的启发,想到了一个算法.首先,我一开始是摸不着头脑,只是明白了按规则最多应该有N*(N-1)/2场比赛[每组一个人],最少应该有N-1场比赛[一组一个人,其他人一组].或者0场比赛[所有人一组].后来换个角度来考虑,觉得不应该从有K场比赛,如何分这N个人来考虑.应该考虑一下有N个人,如何分组才能有这K场比赛.另外,也不应该把所有人分在一组,然后分开一个,然后再一个...这样反倒没有规律了.后来想到如果一开始是每一个人一组,然后没人之间都有比赛这样就是一个完全无向图.而合并一组就是把组内的边除去.也就是m个人分为一组的话,就从N阶完全无向图中除去一个m阶完全无向图.
就这样一直合并直到能得到K条边为止,或者只能得到一个小于K的边数.至于具体的算法我还没写出来^_^!! 同时也不知道这个算法是否可行.拭目以待了^_^!!
2007年3月12日星期一
关于Astar2006-3变态比赛规则的进一步讨论
首先,关于题目的补充要求(我们老师没有这样的要求,只是要求算法尽量的优化就可以了):
1．程序将运行在一台Linux机器上（内存使用不作严格限制），在每一测试数据集上运行不能超过10秒，否则该用例不得分；
2．要求程序能按照输入样例的格式读取数据文件，按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据，该题将不得分；
3．该题目共有3个测试数据集，每个测试数据集为一个输入文件。各测试数据集占该题目分数的比例分别为30%，30%，40%；
经过考虑我把题目抽象为N个元素,分为m组.每组人数为A1,A2,......,Am(均不为空[≠0]).其中
A1+A2+...+Am=N
A1(N-A1)+A2(N-A1-A2)+...+Am(N-A1-A2-...-Am)=K
用递归来解决,每次递归k值都在减少Am(N - Am),基于以上公式对Am递增,递归,回溯所有组合即可得出答案
在网上搜到一位牛人的文章中这样说: 这题我是O(n^4)的记忆化搜索。用了一种技巧合并状态。所以复杂度估计也只有O(N^3), 跑出所有数据在自己机上是5s.代码写的相对简单漂亮 呵呵,真想知道他这个算法是怎样的一个算法.
1．程序将运行在一台Linux机器上（内存使用不作严格限制），在每一测试数据集上运行不能超过10秒，否则该用例不得分；
2．要求程序能按照输入样例的格式读取数据文件，按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据，该题将不得分；
3．该题目共有3个测试数据集，每个测试数据集为一个输入文件。各测试数据集占该题目分数的比例分别为30%，30%，40%；
经过考虑我把题目抽象为N个元素,分为m组.每组人数为A1,A2,......,Am(均不为空[≠0]).其中
A1+A2+...+Am=N
A1(N-A1)+A2(N-A1-A2)+...+Am(N-A1-A2-...-Am)=K
用递归来解决,每次递归k值都在减少Am(N - Am),基于以上公式对Am递增,递归,回溯所有组合即可得出答案
在网上搜到一位牛人的文章中这样说: 这题我是O(n^4)的记忆化搜索。用了一种技巧合并状态。所以复杂度估计也只有O(N^3), 跑出所有数据在自己机上是5s.代码写的相对简单漂亮 呵呵,真想知道他这个算法是怎样的一个算法.
[转贴] 写的很好啊 幽默~~ 心声~~
Five reasons why you should marry me
A friend sent me the following in an email. It is so numerically funny.Five reasons why you should marry me -
1. I am a mature, responsible adult now:
2. I am a nice gentlemen, everyone likes me:
3. so many things I enjoy, spending time with you is my first choice:
4. I am the only one that matches you !
5. I love to save the world. Let us do it together !
A friend sent me the following in an email. It is so numerically funny.Five reasons why you should marry me -
1. I am a mature, responsible adult now:
2. I am a nice gentlemen, everyone likes me:
3. so many things I enjoy, spending time with you is my first choice:
4. I am the only one that matches you !
5. I love to save the world. Let us do it together !
2007年3月11日星期日
作业题
AStar2006百度之星程序设计大赛试题
相信作为编程高手的你一定知道该怎么回答这个问题了吧？ 那么现在请你帮助W.Z吧。
3.变态比赛规则 为了促进各部门员工的交流，百度举办了一场全公司范围内的“拳皇”（百度内部最流行的格斗游戏）友谊赛，负责组织这场比赛的是百度的超级“拳皇”迷W.Z。W.Z不想用传统的淘汰赛或者循环赛的方式，而是自己制定了一个比赛规则。
由于一些员工（比如同部门或者相邻部门员工）平时接触的机会比较多，为了促进不同部门之间的交流，W.Z希望员工自由分组。不同组之间的每两个人都会进行一场友谊赛而同一组内的人之间不会打任何比赛。
比如4个人，编号为1~4,如果分为两个组并且1，2一个组，3，4一个组，那么一共需要打四场比赛：1 vs 3，1 vs 4，2 vs 3，2 vs 4。 而如果是1，2，3一组，4单独一组，那么一共需要打三场比赛: 1 vs 4，2 vs 4，3 vs 4。
很快W.Z意识到，这样的比赛规则可能会让比赛的场数非常多。W.Z想知道如果有N个人，通过上面这种比赛规则，总比赛场数有可能为K场吗？比如3个人，如果只分到一组则不需要比赛，如果分到两组则需要2场比赛，如果分为三组则需要3场比赛。但是无论怎么分都不可能恰需要1场比赛。相信作为编程高手的你一定知道该怎么回答这个问题了吧？ 那么现在请你帮助W.Z吧。
输入要求：
每行为一组数据，包含两个数字 N, K( N∈(0，500] K∈[0,＋∞) )。例：
2 0
2 1
3 1
3 2
输出要求：对输入的N,K 如果N个员工通过一定的分组方式可以使比赛场数恰好为K，则输出"YES"，否则输出"NO"（请全部使用大写字母），每组数据占一行。例：
YES
YES
NO
YES
这就是这个学期的课程设计的变态题目了，完完全全是一个解决问题的算法题目。寒假里恶补的数据库看来是用不上了。今天才拿到这个题目，没有头绪勒。看看再说吧
订阅：
博文 (Atom)