找回密码
 欢迎注册
查看: 16646|回复: 6

[求助] 一个设计问题

[复制链接]
发表于 2008-3-28 14:03:40 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
初来乍到,问个问题,这个不是什么竞赛题,使平时研究中遇到的:

有奇数n=3k+1个顶点,围成一个圆,把这些点分别组成k个三角形,会有一个多余的点。
每个三角形的边长定义为两点在圆上的距离。按不同方向,每两个点在圆上显然会有两个距离,取较小的那个。
这样,圆上任意两点的距离会大于等于1,小于等于[n/2]
要求:这k个三角形中所有边的集合中,对于1<=i<=[n/2],长为i的恰有2条。
目标:
1、希望可以得到一个构造算法,对任意n构造出解。
2、如果1不行,希望得到一个较高效算法,得到对特定n的解。

我用计算机搜索了一下n比较小的情况,但需要的n较大,比如10000就不知怎么办了。
以上不知说清了吗,谢了先。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-30 10:36:50 | 显示全部楼层

对题目的疑问。。。

  • “有奇数n=3k+1个顶点”——这么说,k必须为偶数了?!
  • “把这些点分别组成k个三角形,会有一个多余的点”——多的这个点为什么?(哦,在要求栏中有交代,才搞明白)
  • “每个三角形的边长定义为两点在圆上的距离”——严格来说,可是两点间之间较短的那段圆弧长度(注意,不是距离)?
  • “这样,圆上任意两点的距离会大于等于1,小于等于[n/2]”———请问,这个“1”单位是什么?相对于圆半径,之比可是定值?
  • “如果1不行”——??
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-31 08:57:19 | 显示全部楼层

谢谢

先谢谢 gxqcn的参与。
1、是的,也可将n表为6x+1
3、可以说是弧长,说距离比较抽象一些
4、这里的弧长是离散概念,如a,b两点间有cde这3个点,那么ab间的距离为4 ,即 a-c-d-e-b,中间的4个间隔。
如果总共有7个点围成圆,即上边的5个加上fg,顺序为a-c-d-e-b-f-g-a,则ab间的距离为3,因为b-f-g-a为3,d=min(3,4)

对于1,2,3,4,5,6,7这7个点顺序围成圈,一种设计为:
(1,5,6),(2,3,7),4为剩余点
这两个三角形的边长均为(1,2,3),所以小于等于[7/2]=3的整数在三角形所有边集合中恰出现两次

表达能力太差,不知说清楚了吗
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-31 09:25:42 | 显示全部楼层
你还不如说原始问题好呢
原始问题是?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-31 09:30:37 | 显示全部楼层
先贴些你的搜索结果和程序看看,这个题目构造感觉挺难,多提供一些数据可能有帮助
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-31 09:35:18 | 显示全部楼层
感觉
http://bbs.emath.ac.cn/thread-174-1-1.html
中结果可以被使用。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-31 09:54:11 | 显示全部楼层
这个就是我的原始问题呀。
你所指的原始问题是想了解我为什么会要思考这个问题吧。
如果上纲上线,会映射到很大的问题。
大家都想解P&NP,于是有人研究hamilton回路,这个问题太难,于是有人研究匹配的规律。有一个图伦问题叫做P1F,是所谓完美1因子分解。这是个40多年的open问题。他在编码理论中构造MDS码有用。MDS码中又有无数的open问题,其中之一是对P1F推广。我就研究这个。
我是搞应用的,所以也不期望就解决的如何如何,但需要算出足够大的值。所以对上面可解的n希望算得越大越好。
各位是应用计算的高手,我想可能会比我算的大得多。

如果可以对任意n或者某个特殊无穷数列(如素数的某个函数)构造出来,我认为那将是一个不错的结论,呵呵,你写论文发表,将结果告诉我,我好来引用。
如果算的比我大一些,那么我就恬不知耻的将结果据为己有,顶多提及各位姓名并感谢一番。
如果比我大出数量级,我有机会请你吃龙虾。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-28 17:39 , Processed in 0.044239 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表