用一个有理数表示三个有理数
如何将三个有理数变成一个有理数，并且可以从这个有理数还原成原来的那三个有理数。
用算法来描述，就是求两个算法：T1、T2，
算法T1：输入：有理数 A、B、C
输出：有理数 Q
算法T2：输入：有理数 Q
输出：有理数 A、B、C
要求T1的输出经过T2的计算后还原为T1的输入。
我已经解决了这个问题，现在写出来考考大家。:)
问题点数：100、回复次数：78Top
1 楼zzwu（未名）回复于 2005-04-03 18:10:51 得分 0
很有意思的问题！Top
2 楼antter（JiangMiao）回复于 2005-04-03 19:24:38 得分 0
在精度不变的情况下没有误差，没有可能。否则.rar文件还能再压缩成原来的1/3Top
3 楼wuyi8808（空间/IV）回复于 2005-04-03 19:33:31 得分 0
在精度不变的情况下没有误差，我就做到了。和“.rar文件还能再压缩成原来的1/3”没有关系。
Top
4 楼galois_godel（）回复于 2005-04-03 20:16:46 得分 10
这个问题其实就是说 在 Q^3 和 Q之间找一个一一的映射
由于 Q^3 和Q 都是可数集，所以这个映射必定存在Top
5 楼galois_godel（）回复于 2005-04-03 20:19:35 得分 10
其实也不要说是 Q^3 ，就是Q^n 也对的
也就是说 楼主即使把 A、B、C改成 A1,A2,....,An
这两个变化还是能够被找到的Top
6 楼MagicCarmack（MagiC++）回复于 2005-04-03 21:03:35 得分 0
好题Top
7 楼antter（JiangMiao）回复于 2005-04-03 21:13:08 得分 0
在精度限制(比如double是16位有效数)的情况下：
假设为每个数最多是1位
3个数则有3位，要使3位的数通过某种关系与另一个1位的数对应，
3位的数有8种可能性，1位的数有两种可能性，则至少有6个数不1位的数确定
讲了那么多话，简言之就是 容斥原理。
如果允许有误差的话可以用Hopfield联想记忆网络，从Q联想到A,B,C就可以了。Top
8 楼antter（JiangMiao）回复于 2005-04-03 21:15:39 得分 0
- - 刚发现进错房间了，以为是在c++版块，既然是学术讨论自然是无精度限制了 @_@Top
9 楼wuyi8808（空间/IV）回复于 2005-04-03 21:29:04 得分 0
这个问题其实就是说 在 Q^3 和 Q之间找一个一一的映射
由于 Q^3 和Q 都是可数集，所以这个映射必定存在
其实也不要说是 Q^3 ，就是Q^n 也对的
也就是说 楼主即使把 A、B、C改成 A1,A2,....,An
这两个变化还是能够被找到的
--------------------------------------------------------------------
galois_godel() 分析得相当透彻，原命题对有限个有理数也是成立的。
不过根据我的原题，不要求是一一映射，只要是 Q^n 到 Q 之间的可逆映射就够了。
Top
10 楼arrowcy（长弓手）回复于 2005-04-03 23:12:23 得分 0
不过这里的学术讨论也是建立在计算机的基础上的，如果不考虑精度问题的话，任意数字都可以表示n个数字，只要你写出n个函数就行了Top
11 楼arrowcy（长弓手）回复于 2005-04-03 23:18:18 得分 0
在精度不变的情况下没有误差，我就做到了。和“.rar文件还能再压缩成原来的1/3”没有关系
=====================================================
如果能够用1个数表示3个数，而且精度不变的话，肯定就可以把rar文件（任何一种文件都可以）用你说的这种算法压缩到原来的1/3，因为把rar文件里面的每三个一定长度的字节当成三个数，就可以用一个数字来表示，而这个数字和原来数字的精度相同，所以应该是能够用同样长度的数据来表示，所以就压缩到了原来的1/3了Top
12 楼wuyi8808（空间/IV）回复于 2005-04-03 23:40:08 得分 0
我理解的精度不变的意思是不损失有理数精度，比如说1/3就是1/3，而不是用0.33333333333333333333...来表示，小数点后面有多少位都不行。
我说的有理数是数学上的有理数，而不是计算机中的浮点数。
诚如galois_godel()分析的那样可以把n个有理数用一个有理数来表示，这与文件的压缩没有关系。否则的话，要是取n=1000000，岂不是可以把文件压缩到原来的百万分之一了？
Top
13 楼wuyi8808（空间/IV）回复于 2005-04-03 23:45:21 得分 0
不过这里的学术讨论也是建立在计算机的基础上的，如果不考虑精度问题的话，任意数字都可以表示n个数字，只要你写出n个函数就行了
-----------------------------------------------------------------------
To: arrowcy(长弓手)，请理解原命题的意思。我的意思是我已经写出了符合要求的算法T1、T2，你如果也得出了T1、T2，请贴出来。
Top
14 楼mmmcd（超超）回复于 2005-04-04 10:24:52 得分 0
很有意思
一时还没思路Top
15 楼dengsf（drklnk@Radical_Dreamer）回复于 2005-04-04 11:08:47 得分 0
不知对效率的要求高不高？还是仅要求可行？
还有 A,B,C 是否有序？
Top
16 楼wuyi8808（空间/IV）回复于 2005-04-04 16:26:33 得分 0
算法T2输出的 A,B,C 要求是和算法T1输入的 A,B,C 是相同顺序的。
把算法在纸上写出来就行，不要求用计算机程序实现，因为实际的计算机所能存储的数的大小和精度是有限的，而我们在这里研究的是理论上的有理数。
我实现的算法T1、T2的效率很好，把算法写在纸上，用手算就可以算得出来。
Top
17 楼mmmcd（超超）回复于 2005-04-05 08:56:07 得分 20
我的一点不成熟想法：
自然数:
1 2 6 7 15 16 28 29
3 5 8 14 17 27 30
4 9 13 18 26 31
10 12 19 25 32
11 20 24 33
21 23 34
22 35
36
...
有理数:
1/1 1/2 1/3 1/4 1/5 1/6 1/7
2/1 2/2 2/3 2/4 2/5 2/6
3/1 3/2 3/3 3/4 3/5
4/1 4/2 4/3 4/4
5/1 5/2 5/3
6/1 6/2
7/1
...
建立有理数到自然数的函数：
f(a/b) => n
建立自然数到有理数的函数：
t(n) => a/b
T1: Q=f(f(f(A)/f(B))/f(C))
T2: C=t(t(Q)的分母)
x=t(t(Q)的分子)
B=t(t(x)的分母)
A=t(t(x)的分子)
一定还有更好的Top
18 楼microblue（）回复于 2005-04-05 09:38:35 得分 20
设 abs(A) = p1/q1, abs(B) = p2/q2, abs(C) = p3/q3,
令 p4 = (sign(A)+2)*100 + (sign(B)+2)*10 + sign(C)+2
令 D 是不小于 max(p1, q1, p2, q2, p3, q3, p4) + 1 的最小素数。
令 E = p4 + p3 * D + q3 * D^2 + p2 * D^3 + q2 * D^4 + p1 * D^5 + q1 * D^6
令 F = E/D
则 F 为所求的有理数。
Top
19 楼wuyi8808（空间/IV）回复于 2005-04-05 12:49:52 得分 0
To: microblue(microblue)
令 p4 = (sign(A)+1)*9 + (sign(B)+1)*3 + (sign(C)+1) + 1
岂不更好？
补充一下：
sign(x) = -1, 如果 x < 0
= 0, 如果 x = 0
= 1, 如果 x > 0
Top
20 楼wuyi8808（空间/IV）回复于 2005-04-05 13:04:46 得分 0
To: mmmcd(超超)
想法很好。把“/”改成“,”似乎更合适，因为在
T1: Q=f(f(f(A)/f(B))/f(C))
中不能进行约分，否则就糟糕了。
建立(a,b)到自然数的函数：
f(a,b) => n
建立自然数到(a,b)的函数：
t(n) => (a,b)
T1: Q=f(f(f(A),f(B)),f(C))
T2: C=t(t(Q)的b)
x=t(t(Q)的a)
B=t(t(x)的b)
A=t(t(x)的a)
Top
21 楼wuyi8808（空间/IV）回复于 2005-04-05 13:16:33 得分 0
其实我做出的算法是：
“用一个自然数表示有限个有理数”
见：http://blog.skyiv.com/more.asp?name=air&id=50
Top
22 楼ckc（火）回复于 2005-04-05 14:04:32 得分 0
很简单，参考计算机表示有理数的方法把这N个数转换成固定长度的数据
然后拼到一起，直接转换成最终的结果就OK了Top
23 楼zzwu（未名）回复于 2005-04-05 14:39:10 得分 0
没有要求从任何一个有理数分解为3个有理数吗？如果这样，情况就完全两样了！Top
24 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2005-04-05 15:27:56 得分 0
有理数都可以表示成为分数的形式a/b其中a和b都是整数
最简单的方法把整数串起来就是了ab，这个是一个长的整数。
再多也是可以串连的
Top
25 楼Smile_Tiger（笑面虎）回复于 2005-04-05 15:50:24 得分 0
to happy__888([顾问团]寻开心):
|-
有理数都可以表示成为分数的形式a/b其中a和b都是整数
最简单的方法把整数串起来就是了ab，这个是一个长的整数。
再多也是可以串连的
-|
那你怎么逆运算回去阿？
Top
26 楼Smile_Tiger（笑面虎）回复于 2005-04-05 15:55:23 得分 0
不过 happy__888([顾问团]寻开心) 的想法可以转换为 一个编码过程
设定T1算法就是对3个数进行编码，编码用到的字符集只能是'0'-'9',得到一个大数
T2就是解码过程
...Top
27 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2005-04-05 16:09:00 得分 0
其实这里面存在的是两类对应关系
在大学数学系的《实变函数与泛函分析》课程当中有提到这两类关系
第1类 有理数和自然数的对应关系
第2类 多维自然数和自然数之间的对应关系
其实这两类就是超超表示的关系
他的第一个示例就是 多维和一维之间如何建立一一对应关系，他给的例子实二维和一维之间的关系
第二个例子就是有理数和自然数之间的对应关系
利用第一类关系，每个有理数都有了一个自然数和它对应
按照第二类关系，类似可以建立起三维数组和自然数之间的对应关系，
这样就完整的解决了问题了。
其实完全可以扩展到一个整数和N个自然数的一一对应关系的
Top
28 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2005-04-05 16:09:48 得分 0
在数学上，只是可数集之间的一一对应关系的建立方法而已Top
29 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2005-04-05 16:42:58 得分 0
在数学上，能够和自然数集合建立一一对应关系的集合都成为可数集合
1 首先自然数是可数集合，这个很显然的，自然数到自然数之间必然是有限的集合
2 整数也是可数集合, 下面就是整数和自然数集合之间的一种对应关系
... -5 -4 -3 -2 -1 0 1 2 3 4 5 ....
... 10 8 6 4 2 0 1 3 5 7 9 ....
3 自然数组成的二维数组也是可数集合 {x,y | x, y 属于 N }
0 1 2 3 4 ......
0 0 1 3 6 10
1 2 4 7 11
2 5 8 12
3 9 13
4 14
从这个表当中，任意给出一个点对，比如(2,3), 可以找到一个自然数和他对应，比如12。
4 多维的自然数组成的集合也是可数的集合
利用二维变一维的方法，每次减少一个维数了。
5 有理数是可数的集合
因为有理数可以表示成为二维的点对，有理数可以分解成为两个整数的除法，而且是一一对应的
显然，楼主的问题，可以利用，有理数是可数集合的办法，找到每个有理数对应的自然数
多个有理数，三个，对应的是三维的数组，利用多维到一维的办法，自然还可以找到一个唯一的自然数和他对应的
注意前面描述的对应关系都是一一对应的，因此这个答案自然也是存在的。
这个是从数学理论上解决这个问题的办法
10多年没有看，这个《实变函数与泛函分析》的书了，也记忆得不太清楚
详细的定义，还是建议看那本书去吧
和可数集合对应的是不可数集合，比如无理数集合
还有比无理数集合更高等级的集合，比不可数还不可数的集合，好像叫做无穷集合吧，忘记了。Top
30 楼zzwu（未名）回复于 2005-04-05 17:16:12 得分 20
续上面我的发言：
举个例子，设有3个有理数为：
1/2，2/3，-3/4
将此数作为一个字符串,S:
"1/2，2/3，-3/4"
然后进行编码，不妨就用ASCII码：
/ , - 0 1 2 3 4 5 6 7 8 9
64 39 45 48 49 50 51 52 53 54 55 56 57
则整个串 S 的代码是：C = “49645039 ...3945516452”
显然，此编码是一个整数，自然也是一个有理数, 这样就说明三个有理数可以变成一个有理数。
反之，从这个有理数很容易分离出每一位ASCII码：
49 64 50 39 ... 39 45 51 64 52
由此可知每一个符号为：
1 / 2 ， ... ， - 3 / 4
这样，就可以得到原来的3个有理数了：1/2,...,-3/4
Top
31 楼zzwu（未名）回复于 2005-04-05 17:19:32 得分 0
本质上就是：任何信息可以用数字来编码！Top
32 楼zzwu（未名）回复于 2005-04-05 17:23:44 得分 0
可以推广为：
任何n个有理数都可以变成一个有理数，并且可以从这个有理数还原成原来的那n个有理数。
Top
33 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2005-04-05 17:40:35 得分 0
zzwu的说法，和我原来的a/b串连成ab的说法都是另类的解决办法
但是，都存在一个没有明确说明的问题： 如何分割这几个数字的问题，必须有特殊的地方来分开
串起来容易，再拆开的依据是什么
当然我们可以定义各种方法，比如仿照字符串的方法，前面用一个数表示每个子串的长度
Top
34 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2005-04-05 18:05:27 得分 0
如果存在这样的方法，可以分割整数到不同的字符串，这个分割符号必然是占位的
这样，对于整个数的长度来说，就有了影响，这个数字除了组成它的各个有理数之外
还包含了’额外‘的分隔符
这样的效果，看起来是没有用一一映射关系建立起来的结果完美。Top
35 楼zzwu（未名）回复于 2005-04-05 18:30:50 得分 0
分开数的地方就是逗点啊！
它的代码绝对不会和0-9十个数字的代码还起来的.Top
36 楼wuyi8808（空间/IV）回复于 2005-04-05 20:14:45 得分 0
将此数作为一个字符串,S:
"1/2，2/3，-3/4"
然后进行编码，不妨就用ASCII码：
/ , - 0 1 2 3 4 5 6 7 8 9
64 39 45 48 49 50 51 52 53 54 55 56 57
则整个串 S 的代码是：C = “49645039 ...3945516452”
显然，此编码是一个整数，自然也是一个有理数, 这样就说明三个有理数可以变成一个有理数。
反之，从这个有理数很容易分离出每一位ASCII码：
49 64 50 39 ... 39 45 51 64 52
---------------------------------------------------------------------------------
zzwu(未名)的方法很好，是我所见过的最简单的方法，适用有限个有理数，还原也非常简单，每两位数一断，然后作为ASCII码解释成字符串就可以了。
佩服！
Top
37 楼wuyi8808（空间/IV）回复于 2005-04-05 20:29:12 得分 0
0 1 2 3 4 5 6 7 8 9 / , -
0 1 2 3 4 5 6 7 8 9 10 11 12
当然，也可以如上编码，当作13进制数来看。
只不过编码时要把13进制整数换算成10进制整数，解码时又要把10进制整数换算成13进制整数，比较麻烦，还是zzwu(未名)原来的方法(其实可以看作是100进制)来得快速直观。
Top
38 楼wuyi8808（空间/IV）回复于 2005-04-05 20:31:14 得分 0
没有要求从任何一个有理数分解为3个有理数吗？如果这样，情况就完全两样了！
-----------------------------------------------------------------------------
zzwu(未名)这句话问得好，抓住了问题的本质。
Top
39 楼dengsf（drklnk@Radical_Dreamer）回复于 2005-04-06 13:19:31 得分 0
还以为楼主纯粹是从计算上玩把戏～～Top
40 楼cuixiping（无心●愚公）回复于 2005-04-07 01:46:48 得分 0
只要不嫌位数太长，只要3个有理数的最大位数是预知的，就容易办。
如：知道A、B、C的分数表示时，分子分明都最多50位，用100位可以表示A、B、C的每一个。
把三个机械的拼起来，就是一个300位的Q。拆也很好拆啊。
换句话说，把3个数都化为分数形式，对分子分母的前面补0，使得所有分子分母的位数等于其中3个分子和3个分母之中最长的一个，然后机械的拼起来。
不一定高效，但简单。
例子： A=1/3 B=2/17 C=44/7897
补0后： A=00010003 B=00020017 C=0044/7897
得到Q: Q=000100030002001700447897
要从Q得到A、B、C也容易，等拆6等分，分别是每个的分子分母。
我只是举例说明，实际中可以化为二进制后的位数。最前面的0可以去掉，那么还原的时候就要将位数补为6的整数倍，然后就得到该怎么拆了。
Top
41 楼beyondong（查拉斯图拉）回复于 2005-04-07 07:50:29 得分 0
只要不嫌位数太长，只要3个有理数的最大位数是预知的，就容易办。
如：知道A、B、C的分数表示时，分子分明都最多50位，用100位可以表示A、B、C的每一个。
把三个机械的拼起来，就是一个300位的Q。拆也很好拆啊。
换句话说，把3个数都化为分数形式，对分子分母的前面补0，使得所有分子分母的位数等于其中3个分子和3个分母之中最长的一个，然后机械的拼起来。
不一定高效，但简单。
例子： A=1/3 B=2/17 C=44/7897
补0后： A=00010003 B=00020017 C=0044/7897
得到Q: Q=000100030002001700447897
要从Q得到A、B、C也容易，等拆6等分，分别是每个的分子分母。
我只是举例说明，实际中可以化为二进制后的位数。最前面的0可以去掉，那么还原的时候就要将位数补为6的整数倍，然后就得到该怎么拆了。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
其实也可以变成一个分式，请看这个例子，
例如：25，-4/7，-55/56
变为：025104155/001007056
就是原数的各个分子或分母合并到新数的分子或分母中，其中
用0表示正数，1表示负数，就是每个原数的分子或分母都增加一位符号位。
并且使各个原数的分子或分母个数相同，不同的用零补全。
恢复时只要注意一下符号位就行拉
Top
42 楼cuixiping（无心●愚公）回复于 2005-04-07 10:18:50 得分 0
忘了符合位了，那就多补一位吧，0表示正，1表示负，如下：
例子： A=-1/3 B=2/17 C= 44/7897
补0后： A=1000100003 B=0000200017 C=0004407897
得到Q: Q=1000100003000002000170004407897Top
43 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2005-04-07 11:48:35 得分 0
我觉得大家没有从问题的本意上去考虑它
这个问题的核心就是不引入分隔符号
否则，这样的问题的答案多如牛毛了
比如：
把表达3个有理数的6个整数串连起来，中间加入分割符号，组成字符串，当成二进制来理解就可以了
可是这样的做法，你得到的是什么，你还可以认为它是原来的问题域当中的整数吗
Top
44 楼cuixiping（无心●愚公）回复于 2005-04-08 16:02:41 得分 0
楼上的，你没看清楚吧？
Top
45 楼zzwu（未名）回复于 2005-04-08 23:24:59 得分 0
三个有理数,不用分隔号,是不可能区分出它们来的.例如: 1/234/455/666
是 1/2 34/456 7/666 呢?
还是 1/23 4/45 67/666 呢?
或者还是 1/2 34/45 5/666 呢? 等等
Top
46 楼Kusk（Kusk）回复于 2005-04-10 16:11:49 得分 0
3.14000000000000000000...
0.06150000000000000000...
5.00000000000000000000...
==>
305.1004600100500000000000000000000000000...
这里，只考虑非负有理数（亦可包括非负实数），如果把负有理数（实数）也考虑进去，在首位加一个8bits信息量的符号位即可。Top
47 楼zzwu（未名）回复于 2005-04-10 17:34:22 得分 0
用无穷位来表示吗？这样一来无理数也可以3合1了！Top
48 楼zzwu（未名）回复于 2005-04-10 17:41:29 得分 0
你这样还不行，因为怎样来表示大整数呢？比如
X=11111111111111...
Y=0.0000000000001...
Z=3333333333.333333333...
Top
49 楼cuixiping（无心●愚公）回复于 2005-04-11 00:56:57 得分 0
to zzwu(未名) :
你是误会楼主的意思了。
--------------------------------------------------------
3个有理数 转化为一个有理数之后是
--------------------------------------------------------
X Y Z F
--------------------------------------------------------
1/2 34/456 7/666 000100020034045600070666
1/23 4/45 67/666 000100230004004500670666
1/2 34/45 5/666 000100020034004500050666
--------------------------------------------------------
怎么可能分不出来呢？
没用分隔号啊。
F的数字串平均分成六段，分别是分子分母了嘛，真是。
--------------------------------------------------------
Top
50 楼zzwu（未名）回复于 2005-04-11 10:13:53 得分 0
TO cuixiping(无心):
我不是对你的问题，而是针对 Kusk(Kusk) 的方法提问，
没有讲清，抱歉！
Top
51 楼mathe（）回复于 2005-04-14 13:13:09 得分 0
这种映射太多了，也很容易构造，我给出一个一一对映的变换吧。
任何有理数都可以写成一个周期循环小数（如果是有限小数，把后面的周期全部看成0就可以了）
现在如果有三个有理数x,y,z分别为
x*10^s=x(-k)x(-k+1)..x(-1).x(1)x(2)....x(n)x(1)x(2)...x(n)...
y*10^s=y(-k)y(-k+1)..y(-1).y(1)y(2)....y(n)y(1)y(2)...y(n)...
z*10^s=z(-k)z(-k+1)..z(-1).z(1)z(2)....z(n)z(1)z(2)...z(n)...
其中n为x,y,z最小正周期的公倍数,s是x,y,z中小数点后没有循环部分最大的程度，k是x,y,z不循环部分最大的长度。我们将这三个数映射为一个周期为3n的有理数就可以了：
w*10^3s=x(-k)y(-k)z(-k)x(-k+1)y(-k+1)z(-k+1)...x(-1)y(-1)z(-1).x(1)y(1)z(1)x(2)y(2)z(2)...x(n)y(n)z(n)x(1)y(1)z(1)x(2)y(2)z(2)...x(n)y(n)z(n).....Top
52 楼Kusk（Kusk）回复于 2005-04-16 00:59:24 得分 0
回复人：zzwu(未名) ( 两星(中级)) 信誉：113 2005-4-10 17:41:29 得分:0
?
你这样还不行，因为怎样来表示大整数呢？比如
X=11111111111111...
Y=0.0000000000001...
Z=3333333333.333333333...
-----------------------------------------------
在较小数的前面补足0,使之与Z对齐之后再合并，这样(位数可能与你的例子不一样，懒得数了：))：
1111111111111111111111...111.0000000000000...
0000000000000000000000000000.0000000000001...
0000000000000000333333333333.3333333333333...
然后再同理合并。Top
53 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2005-04-18 11:46:40 得分 0
to 楼上的，zzwu的方法是没有问题的，而且是很直观容易做到的
有理数都是有限循环的的，也都是可以表示成为分数的，然后就可以了
Top
54 楼Kusk（Kusk）回复于 2005-04-18 12:07:59 得分 0
回复人：happy__888([顾问团]寻开心) ( 两星(中级)) 信誉：124 2005-04-18 11:46:00 得分:0
?
to 楼上的，zzwu的方法是没有问题的，而且是很直观容易做到的
有理数都是有限循环的的，也都是可以表示成为分数的，然后就可以了
-----------------------------------------------------------
这点我很赞同，也很欣赏这样的思路。我只是针对zzwu的提问做出尝试性的解答而已。考虑不一定成熟，所以拿出来也让大家探讨一下。Top
55 楼quicmous（快鼠）回复于 2005-04-18 13:06:05 得分 0
三个有理数：
A=111.111
B=222.222
C=333.333
映射成：
X=123123123.123123123
这个映射是一一映射。
Top
56 楼quicmous（快鼠）回复于 2005-04-18 13:08:41 得分 0
上面的映射规则是康托为证明空间上的点和直线上的点等势而构造的，正好可以解决搂主的问题。Top
57 楼quicmous（快鼠）回复于 2005-04-18 13:10:17 得分 0
不仅证明了有理数可以满足楼主的要求，而且对于任意的实数也是如此。Top
58 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2005-04-18 13:38:14 得分 0
从有理数转换到分数恐怕是必须要做的
否则你无法区分那个是循环小数，那个是定长的小数呢
别忘记是用整数表达这个三个有理数
如果不考虑空间浪费的问题，zzwu的方法就是通用的方法，后续其他的人的解法实际上都没有脱离他的编码的范畴的。
Top
59 楼xdspower（杂食菜熊）回复于 2005-04-18 14:36:57 得分 0
zzwu(未名)提到
-------------------------------------------------------------
三个有理数,不用分隔号,是不可能区分出它们来的.例如: 1/234/455/666
是 1/2 34/456 7/666 呢?
还是 1/23 4/45 67/666 呢?
或者还是 1/2 34/45 5/666 呢? 等等
-------------------------------------------------------------
其实不一定是这样的，在很多领域有时字符设置是有限的，就需要利用有限的字符来设计标记，比如这个情况下，因为不可能存在//的有理数，就可以
1/2//34/45//5/666采用这样的方法来实现分割，甚至正负号也可以这样表示比如采用///，这样的应用在数据传送中是经常采用的。
Top
60 楼quicmous（快鼠）回复于 2005-04-18 18:33:15 得分 0
针对楼主问题给出一个解
========================================
楼主问题：
算法T1：输入：有理数 A、B、C
输出：有理数 Q
算法T2：输入：有理数 Q
输出：有理数 A、B、C
-------------------------------------
由于有理数可以用两个整数表示(即分数表示)，因此问题可以归结为三个整数是否可以一一映射到一个整数的问题。下面就整数情况给予讨论：
设
A = a[0] + 10*a[1] + 10^2*a[2] + 10^3*a[3] + ...+ 10^X*a[X]
B = b[0] + 10*b[1] + 10^2*b[2] + 10^3*b[3] + ...+ 10^Y*b[Y]
C = C[0] + 10*c[1] + 10^2*c[2] + 10^3*c[3] +... + 10^Z*c[Z]
W = max(X, Y, Z)
则
Q = 10^0*a[0] + 10^1*b[0] + 10^2*c[0]
+ 10^3*a[1] + 10^4*b[1] + 10^5*c[1]
+ ...
+ 10^3*W*a[W] + 10^(3*W+1)*b[W} + 10^(3*W+2)*C[W]。
例如：A=123,B=456,C=789,可以推出：Q=741852963.
同样给出 Q=10,072,630,845,952 可以推出A=2052,B=17345,C=2052
不难证明，按照这个法则确定了三维空间的整数点(A,B,C)和直线上的整数点Q之间的一一映射。
事实上，实三维空间的点(x,y,z)和实数轴上的点P也存在类似的一一映射。
Top
61 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2005-04-18 19:01:41 得分 10
to 快鼠
你的说法和我前面的描述泛函当中的可数集合之间的映射方法当中的一种——三维自然数点对，到一个自然之间的映射关系。
但是需要考虑的是：
1 有理数是用一对整数表示出来的
2 整数还有正有负， 先要把正负数统一用自然数表达出来
3 多个自然数用一组自然数表达
这个题目的完整算法是这样的：
假定 任意给定的有理数e1, e2, e3，已经有一个算法找到它所对应的 分数
这个变换是 F1（）
那么利用F1可以把三个有理数变换成为6个整数(P11, P12) (P21, P22) (P31, P32)
这个F1变换没有公式可写，因为在计算机当中有理数无法精确表达，自然也无法计算进行转换
只能先假定这个公式存在
e1->(P11, P12) e2->(P21,P22), e3->(P31, P32);
构造F2把整数变成自然数
int F2(int p)
{
if ( 0 == p ) return 0;
if ( p>=0 ) return 2*p-1
return -2*p;
}
在F2作用下
(P11，P12)->(N11,N12) (P21, P22)->（N21,N22） (P31,P32)->（N31，N32）
然后构造二维自然数点对点对到自然数的变换N2toN1
int N2toN1(int n1, int n2)
{
int k = n1 + n2;
int base = k * (k-1）/2;
return base + n2;
};
在 N2toN1的变换下， 自然数点对变成了一个自然数了
(N11-N12)->N1, (N21,N22)->N2, (N31, N32)->N3
再构造一个从三个自然数到一个自然数的变换公式
其实这个很简单，调用两次N2toN1就可以了。
int N3toN1(int n1, n2, n3)
{
return N2toN1( N2toN1(n1, n2), n3);
}
这样在N3toN1的变换下，就完成了最终的一个自然数表达的结果
(N1, N2, N3)->N
整个处理流程就是：
F1 ： e1->(P11, P12) e2->(P21,P22), e3->(P31, P32);
F2 ： (P11，P12)->(N11,N12) (P21, P22)->（N21,N22） (P31,P32)->（N31，N32）
N2toN1: (N11-N12)->N1, (N21,N22)->N2, (N31, N32)->N3
N3toN1: (N1, N2, N3)->N
同时注意到上述变换都是可逆的，自然就可以反算的
Top
62 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2005-04-18 19:08:50 得分 5
上面说的是一种在理论上可以不引用任何风格符号，纯粹数学上的解决方法
另外可以引入分割符号，那样会更简单
对应的就是zzwu说的编码问题
无论那种办法，要用计算机表示，都要先默许一种从有理数到分数的转换存在
剩下的就是如何串连了
最简单的串连就是
假定 表示有理数的6个整数是 a b c d e f
直接串连成为字符串 a,b,c,d,e,f
假定a = -1, b= 2, c= 3, d=12345, e=1345, f = -838739
那么串连出来就是 -1,2,3,12345,1345,-828739
这样的字符串
如果把 -和，号都当作特殊的数字理解，加上0到9的数字就是12个不同的数字
把上面的字符串当中12进制的字符串，－符号表示10， ，符号表示11
那么12进制到10进制的转换，在大家经常做过16进制到10进制的转换的情况下不是难题吧
反之当然也存在10到12进制的转换，转换完了，分割开字符串就解决了问题了。
注意，有理数到分数的转换是必须的，否则无法区分表达有理数的有限小数和无限循环小数之间的关系的。
Top
63 楼quicmous（快鼠）回复于 2005-04-19 08:35:05 得分 0
happy__888([顾问团]寻开心) ：
zzwu老兄提供的方法在技术上是可行的，十二进制的想法也很好。
从理论的角度来看，该方法本质上是在做字符串变换，它不能保障Q到A,B,C的逆映射都成功。例如Q="0-9,34,54-243,344,--34"就是一个不合法的序列。即该方法未能保持三维空间和一维空间之间的点之间的一一对应关系
Top
64 楼quicmous（快鼠）回复于 2005-04-19 08:38:16 得分 0
换句话讲，zzwu兄的方法给出的是三维有理坐标到一维有理坐标空间“内”的映射。不能确保每个有理数都能分解成三个有理数。Top
65 楼xiaohaiyan（xiaohaiyan）回复于 2005-04-19 09:28:41 得分 0
Mark.Top
66 楼zzwu（未名）回复于 2005-04-19 10:04:28 得分 0
请各位不要忘记楼主的要求：
“我理解的精度不变的意思是不损失有理数精度，比如说1/3就是1/3，而不是用
0.33333333333333333333...来表示，小数点后面有多少位都不行。“Top
67 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2005-04-19 11:47:09 得分 0
to 快鼠
生成字符串只是一个编码的一个中间步骤
然后通过12进制的理解，转换成为正常的10进制整数加以保存
最终看到的是正常的10进制的整数啊
反之对于一个正常的10进制整数，反向变换成为12进制数，然后再分解它
需要注意的是，这种方法并没有建立一一映射关系，从任意的三个有理数，可以对应出来一个唯一的整数；反之，任何一个整数可不一定能够找到合适的分解，但是对于从三个有理数转换过来的整数是可以反向变换回去的，这就满足了楼主的要求了。就楼主的题目而言，要求的并不是一一映射。
前面的我的方法是一一映射，每三个有理数都可以对应出来一个整数，反之每个整数也可以对应出来唯一的一组三个有理数。
Top
68 楼quicmous（快鼠）回复于 2005-04-20 08:27:09 得分 5
to zzwu(未名)，happy__888([顾问团]寻开心)
这个问题本身和楼上的所有解法给出了一个很有意思的逻辑怪圈。
一方面这个问题看上去是一个数值问题，楼主似乎也很关系算法的精度问题。其实，就本问题而言，其本质是字符串变换问题，可能根本不涉及数值精度变换。
另一方面，许多解法表面上是基于字符串的，而具体过程却又是存数值的。例如，楼上的十二进制方法。
因为可以认为所有的计算机问题都是基于数值计算的，一个算法是否是基于字符串还是基于数值讨论起来意义不大。
但是，如果撇开计算机和一些非本质性的变换，本问题和所有的解法似乎都可以归结为字符串的合成与分解问题。Top
69 楼zzwu（未名）回复于 2005-04-20 08:50:06 得分 0
要在 Q^3 和 Q之间找一个一一的映射自然是不难办到的，
但要考虑所用对角线法的实际可行性，如何保证用有限空间和时间来完成这种1-1映射？
Top
70 楼quicmous（快鼠）回复于 2005-04-20 09:21:06 得分 0
to zzwu(未名)
Q^3 和 Q之间找一个一一的映射不需要采用对角线法，集合论创始人康托给出的办法就简易易行。参见楼上的相关讨论。Top
71 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2005-04-20 11:02:30 得分 0
计算机软件里面的问题，规根到底都是数学问题，这个是勿庸置疑的
单纯从楼主的目的来说，只要能够完成正向和反向的变换都是合格的算法
但是从效率上，一一映射更有价值
编码的方式会引入分隔符之类额外的信息进来
串位合并数据的方法也是可行的，但是这种方法对最终的整数的长度起的影响太大了，相当于3倍最长的数。
Top
72 楼sjjf（水晶剑锋）回复于 2005-05-14 14:21:15 得分 0
markTop
73 楼xiaobingbing（xiaobingbing）回复于 2005-05-16 13:54:36 得分 0
如果从计算机的角度：
每一个有理数的位数相同，
设都为X
那么这个问题是不是就变成了
怎样从一个3*X位和X位的0,1码之间
建立一个一一映射关系Top
74 楼hanweizhouricher（牛）回复于 2005-05-16 18:03:30 得分 0
markTop
75 楼gauss（Powered-by-Internet）回复于 2005-05-22 16:45:22 得分 0
来晚了,说一个笨办法,不知道对不对.
从楼主的归纳“用一个自然数表示有限个有理数”出发,引申到用一个自然数Q表示有限个自然数a1,a2,a3..an.
设从2开始的质数序列是p1,p2,p3....pn(2,3,5,....)
则Q = p1^a1 * p2^a2 * p3^a3 * ...... * pn^an
反过来的算法也是很显然的,因为任意一个大于1的自然数Q总可以按照上面的方式唯一分解,
所以a1,a2....an也总可以唯一地求出来.最笨的办法就是依次除以2,3,5.....多次,并计算次数,这里只是一个计算时间的问题.
解决了一个自然数表示有限个自然数的问题,楼主的问题也自然解决了.
Top
76 楼zzwu（未名）回复于 2005-05-23 09:34:46 得分 0
楼上提供的是一个好办法。
但从有理数到整数之间的转换还不那么简单,因为还要考虑各有理数之间，以及每个有理数的分子和分母之间的分隔问题。Top
77 楼Kvci（看了不笑就没小JJ同时又比较长的昵称__——————————————————————————————）回复于 2005-06-12 05:59:08 得分 0
我的最笨蛋的方法
Q1=86.3 Q2=28.4 Q3=45.5
替换成这个
Q1=86.3 Q2=86.4 Q3=86.5
1000,0110,1010,0011,1111 1000,0110,1010,0100,1111 1000,0110,1010,0101,1111
其中逗号是不必须的，是为了演示分割符合而已
就是把没个数值照译成4位的二进制码，用超过9的部分里的两个编码来分别代表小数点和数字间的分隔。这里1010是代表‘.’,1111代表一个有理数结束。最后整个代码凑起来就是
1000,0110,1010,0011,1111，1000,0110,1010,0100,1111，1000,0110,1010,0101,1111
不要逗号就是
100001101010001111111000011010100100111110000110101001011111
把这个转成10进制的就可以看成一个有理数了。
翻译回去的时候
先把那数倒过来写成二进制形式，
一次读四位进去判断
遇到1010就是小数点，遇到1111就是一个有理数结束。
这个方法简单
实用哦
前面帖子太多了，没有看完，不知道有没有人贴出来
有就见笑了
Top
78 楼fancyf（凡瑞）回复于 2005-06-29 15:15:23 得分 0
这个问题有这么高的讨论价值吗？
存储器中的内容就是一个二进制序列，不可以看作一个大整数吗？一个文件、一块硬盘里面存储的何止3个有理数？只要按照一定的规则去存储、去解析这些二进制序列不就可以了吗？
我把一千个数存在文本文件中，在从文本文件中读出来，这不就是符合要求的T1、T2算法吗？
类似的网络传输、序列化/反序列化、编解码都满足这样的要求
本质上就是用二进制表示其他进制的问题（文本文件的话可以理解为256进制），这在实际中已经用的很多了Top
