变态比赛规则最终版

通过多日的深入研究,终于做成了我的变态比赛规则的最终版!^_^ 其实之前那个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拜托了一个学设计的同学来帮忙.要做就做绝对的专业的!^_^~~

变态比赛规则的优化

知觉告诉我,我的程序的时间复杂度好像已经很小了(具体是多少啊?我不会算~~).但是看到循环里边那个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 <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还有可以改进之处.慢慢来吧~~