！（急！求救）关于一个数学问题的程序实现问题！

tears+ · 发表于 2005-11-15 08:03:07

题目如下： 一条有N个点的线段（已知每个点的距离都是1，且N是偶数） 把自然数（从1开始）往这条线段的N个点上放， 条件是： |Y-X|+D（X，Y）>=N-1 就是任意两个点的数值差的绝对值加上两点间的距离，不小于N-1 求：最后放上的那个数最小可以是多少?lt;br> 这是图论上的一个染色问题，已经困饶我好些日子了，各位大虾高手们研究一下拉 我已有些想法，先把问题放上，下面说我的想法。 恳求各位大虾们帮忙拉。 我的联系方式： email: <a href="http://www.shumo.com/bbs/mailttears@jsmail.hebut.edu.cn" target="_blank" >tears@jsmail.hebut.edu.cn</A> QQ: 2722701

[此贴子已经被作者于2005-11-15 0:12:43编辑过]

tears+ · 发表于 2005-11-15 08:09:31

<

>我现在做法的假设是：
<

>1，前三个点定，从第四个点开始放。
<

>2，放置点的时候只需要考虑其和其前面放的两个点的条件满足既可。

程序如下：
/* main函数仅判断是否偶数，然后调用calcul函数。
 calcul计算函数流程如下： 1、定义变量及结构体 其中，结构体中：re 结果；num 所处位置是第几个 2、对结构体申请空间 3、对申请到空间的结构体初始化(如果输入的是2，则直接输出结果) 4、赋前三个点的值（左、中、右） 5、记下最后赋值的两个点，再赋值的时候只和前两个点比较 6、从(N/2)+2开始，自左向右试，看是否合适，不合适，数加1，继续... 注意：因为程序是从左向右放置合适的数，可能此数还可以放置更向右的另一个位置， 由此可知排列不唯一，但排到最后最大的数是一样的。 7、当没有空位置的时候，跳出，打印... */ 
 #include<stdio.h> #include<stdlib.h>
typedef struct { int re; int num; } node;
/*----------计算函数----------*/ calcul(int n) { int il; int t; int i; int compare1,compare2; int distance; int empty; node *proot,*p,*p1,*p2;
 if(n==2) { printf("(1) 1 "); printf("(2) 1 \n\n"); printf("Want to close this window, press any key."); getch(); return; } 
 proot=(node *)malloc(sizeof(node)*n); /*申请空间*/ if(proot==NULL) return;
 p=proot;
 for(il=1;il<=n;il++) /*清零*/ { p->re=0; p->num=il;
 p++; }
 p=proot; /*赋前三个值*/
 p->re=n/2+1; p2=p;
 t=n/2-1; p=p+t; p->re=1;
 p=proot; t=n-1; p=p+t; p->re=n/2;
 p1=p;
 empty=n-3;
/*----------初始化结束----------*/
 /*----------计算----------*/ p=proot; t=n/2+2;
while(empty!=0) { for(i=1;i<=n;i++) { if(p->re==0) { distance=p->num - p1->num; if(distance<0) distance=-distance; compare1=(t-p1->re)+distance;
 distance=p->num - p2->num; if(distance<0) distance=-distance; compare2=(t-p2->re)+distance;
 if( compare1>=(n-1) && compare2>=(n-1) ) { p->re=t; t++; empty--;
 p1=p2; p2=p; p=proot; break; } } p++; } t++; p=proot; }
p=proot; /*打印*/ for(il=1;il<=n;il++) { printf("(%d) %d ",il,p->re); p++; } printf("\n\n"); printf("The biggest number is: (%d) %d\n\n\n",p2->num,p2->re); printf("Want to close this window, press any key...");
/*----------计算结束----------*/ getch(); return; }
 /*---主函数---*/ main() { int n;
loop: printf("Pleast input a number,n=?\n\n"); scanf("%d",&n); if (n%2==0) { printf("\n\n"); printf("n=%d\n\n",n); calcul(n); } else { printf("\n\n"); printf("this number is not a even number,pleast input again\n\n"); goto loop; }

tears+ · 发表于 2005-11-15 08:16:27

<

>因为我每次都是从左向右遍历，所以有可能这个数值可以放在后面的其他位置，所以不是最优化的
<

>并且我使用的假定也有可能不是最优化的（既前三个点“左为N/2+1，中为1，右为N/2”）。
<

>请高手帮忙。

dahai007 · 发表于 2005-11-15 17:42:11

<

>好手，我来试试看，

		自动登录	找回密码
密码			注-册-帐-号