最省刻度尺设计的组合差集递推算法  

A recursive algorithm of combinatorial difference set design for least scale number on ruler

作　　者：唐保祥[1] 任韩 TANG Baoxiang;REN Han(School of Mathematics and Statistics,Tianshui Normal University,Tianshui 741001,Gansu Province,China;School of Mathematics Sciences,East China Normal University,Shanghai 200062,China)

机构地区：[1]天水师范学院数学与统计学院,甘肃天水741001 [2]华东师范大学数学科学学院,上海200062

出　　处：《浙江大学学报（理学版）》2024年第2期178-185,共8页Journal of Zhejiang University（Science Edition）

基　　金：国家自然科学基金资助项目(11171114)。

摘　　要：在长度为n(n≥2为正整数)的直尺上最少刻多少个刻度就能度量1到n的所有长度,这便是至今未解决的最省刻度尺问题。阐明了最省刻度尺与极小优美图之间的关系,给出了计算最省刻度尺的所有最省刻度值的组合差集递推算法,得到长度为3~40的最省刻度尺的所有最省刻度值,同时,结合图论模型,给出了长度为41~82的最省刻度尺的最省刻度值。For a positive integer n≥2,what is the minimum number of ticks to be engraved on an unscaled ruler of length n to measure all lengths from 1 to n.This is an unsolved problem of ruler with least number of scales.This paper clarifies the relationship between ruler with the least number of scales and the minimal graceful graph,and a combined difference recursive algorithm for calculating all the least scale values of ruler with the least number of scales is given.This algorithm calculates that the length is 3 to all the minimum scale values of the most scale-saving ruler of 40,and combined with the graph theory model,the minimum scale values of ruler with least number of scales with lengths from 41 to 82 are given.

关 键 词：最省刻度尺 优美标号 极小优美图 优美标号算法 组合差集递推算法 

分 类 号：O157[理学—数学] TP301.4[理学—基础数学]