p**s
发帖数: 2707 | 1 给算式 1:2:3:4:5:6:7:8 加上括号，能得到多少个不同的结果？ |
t*******r
发帖数: 22634 | 2 这个冒号是除号的意思？
【在 p**s 的大作中提到】
: 给算式 1:2:3:4:5:6:7:8 加上括号，能得到多少个不同的结果？
|
p**s
发帖数: 2707 | 3 对
【在 t*******r 的大作中提到】
: 这个冒号是除号的意思？
|
p**s
发帖数: 2707 | 4 1/2/3/4/5/6/7/8
这是码工版
【在 t*******r 的大作中提到】
: 这个冒号是除号的意思？
|
C*****d
发帖数: 2253 | 5 63？
【在 p**s 的大作中提到】
: 1/2/3/4/5/6/7/8
: 这是码工版
|
m**n
发帖数: 9010 | 6 这是让小学生做着玩, 看看能找出多少种组合方式的吧?
真要严格的来说, 你怎么加括号, 1后面那个运算只可能是
"/", 但后面的运算就可能由于括号变成"*".
所以问题实际上就是后面六个符号
是"/"还是"*". 简单看(如果不考虑不同的顺序
可能达到相同的结果), 那么就是2^6种.
【在 p**s 的大作中提到】
: 1/2/3/4/5/6/7/8
: 这是码工版
|
C*****d
发帖数: 2253 | 7 60？
【在 C*****d 的大作中提到】
: 63？
|
m**n
发帖数: 9010 | 8 我这个答案是指想加多少括号都可以.
如果只能加一个, 那另说.
【在 m**n 的大作中提到】
: 这是让小学生做着玩, 看看能找出多少种组合方式的吧?
: 真要严格的来说, 你怎么加括号, 1后面那个运算只可能是
: "/", 但后面的运算就可能由于括号变成"*".
: 所以问题实际上就是后面六个符号
: 是"/"还是"*". 简单看(如果不考虑不同的顺序
: 可能达到相同的结果), 那么就是2^6种.
|
C*****d
发帖数: 2253 | 9 至少要算下重复的结果有多少吧
【在 m**n 的大作中提到】
: 这是让小学生做着玩, 看看能找出多少种组合方式的吧?
: 真要严格的来说, 你怎么加括号, 1后面那个运算只可能是
: "/", 但后面的运算就可能由于括号变成"*".
: 所以问题实际上就是后面六个符号
: 是"/"还是"*". 简单看(如果不考虑不同的顺序
: 可能达到相同的结果), 那么就是2^6种.
|
m**n
发帖数: 9010 | 10 懒得算:-)
【在 C*****d 的大作中提到】
: 至少要算下重复的结果有多少吧
|
|
|
p**s
发帖数: 2707 | 11 对，只看最后的结果
【在 m**n 的大作中提到】
: 这是让小学生做着玩, 看看能找出多少种组合方式的吧?
: 真要严格的来说, 你怎么加括号, 1后面那个运算只可能是
: "/", 但后面的运算就可能由于括号变成"*".
: 所以问题实际上就是后面六个符号
: 是"/"还是"*". 简单看(如果不考虑不同的顺序
: 可能达到相同的结果), 那么就是2^6种.
|
t*******r
发帖数: 22634 | 12 不管如何加括号，最后化成一个长分数的话，从 3 开始(包括 3)，每个数要么是在分
子上，要么是在在分母上。(或者好比电路的 pos phase vs neg phase)。
这样首先就是 permutation w/ repetition 的问题，如果先不管相同值的重复，那就
是有 2^6 种 permutation。
下面算重复，prime 不会导致出重复，重复是由 composite 造成的。
俺得先开会去。。。回来再搞。。。
【在 p**s 的大作中提到】
: 1/2/3/4/5/6/7/8
: 这是码工版
|
p**s
发帖数: 2707 | 13 对，先别说怎么做的
【在 C*****d 的大作中提到】
: 60？
|
t*******r
发帖数: 22634 | 14 重复是 phase flip 导致相等，所以这些 flip 的数字 make 1 好像。。。
【在 t*******r 的大作中提到】
: 不管如何加括号，最后化成一个长分数的话，从 3 开始(包括 3)，每个数要么是在分
: 子上，要么是在在分母上。(或者好比电路的 pos phase vs neg phase)。
: 这样首先就是 permutation w/ repetition 的问题，如果先不管相同值的重复，那就
: 是有 2^6 种 permutation。
: 下面算重复，prime 不会导致出重复，重复是由 composite 造成的。
: 俺得先开会去。。。回来再搞。。。
|
t*******r
发帖数: 22634 | 15 (3*8)/(4*6) 构成一个 flippable pattern 一对重复。。。
【在 t*******r 的大作中提到】
: 重复是 phase flip 导致相等，所以这些 flip 的数字 make 1 好像。。。
|
t*******r
发帖数: 22634 | 16 该一对重复，要乘以剩下数字的 permutation w/ repetition，2^(6-4) = 4
4 个 pair 相等，所以目前是
2^6 - 2^(6-4) = 60
下面要证明没有其他相等。
【在 t*******r 的大作中提到】
: (3*8)/(4*6) 构成一个 flippable pattern 一对重复。。。
|
t*******r
发帖数: 22634 | 17 解释一下 make 1 是因为 multiplicative identity 的存在性和唯一性。。。
【在 t*******r 的大作中提到】
: 重复是 phase flip 导致相等，所以这些 flip 的数字 make 1 好像。。。
|
p**s
发帖数: 2707 | 18 应该让你做 1/2/3/.../79/80
【在 t*******r 的大作中提到】
: 解释一下 make 1 是因为 multiplicative identity 的存在性和唯一性。。。
|
t*******r
发帖数: 22634 | 19 你虐待我。。。不过我待会有空试试。。。
【在 p**s 的大作中提到】
: 应该让你做 1/2/3/.../79/80
|
t*******r
发帖数: 22634 | 20 这个其实思路不难，我开会回来写思路，具体计算就算了。
【在 p**s 的大作中提到】
: 应该让你做 1/2/3/.../79/80
|
|
|
t*******r
发帖数: 22634 | 21 开会回来啦。。。俺先把上面那个没有其他重复的证明先给证明
了，然后在 scale up 到 80。。。毕竟搞到 80 体力活比较多，
先把概念在小尺寸级别给搞清楚。。。
【在 t*******r 的大作中提到】
: 这个其实思路不难，我开会回来写思路，具体计算就算了。
|
t*******r
发帖数: 22634 | 22 证明没有其他相等稍微费些口舌，俺就这么简略的说吧。
首先这道题是连续整数 [ 3 ... 8 ]，为了凑那个 1
(multiplicative identity)，这样根据 unique
prime factorization （UPF) ，1 总是可以写成
(p1 * p2 * p3 * ... * pn) / (p1 * p2 * p3 * ... * pn)
而对于楼上和楼下的 primes，搞不同的 association
而形成不重复的数字（显然上下至少要有一个 composite），
就形成一个 flippable pattern。。。另外一个限制条件
是 association 形成的这些数字必须落在 [ 3, 8 ] 之间。
待续。。。
【在 t*******r 的大作中提到】
: 该一对重复，要乘以剩下数字的 permutation w/ repetition，2^(6-4) = 4
: 4 个 pair 相等，所以目前是
: 2^6 - 2^(6-4) = 60
: 下面要证明没有其他相等。
|
t*******r
发帖数: 22634 | 23 这题还有一个陷阱，就是 prime 2 已经出现，后面这个
flippable pattern 不能出现 prime 2。。。不过这个
别阴沟翻船就好了。
然后按 prime 的数目递增开始凑：
(为了方便起见，这里假设对 prime 排序，
p1 <= p2 <= p3 <= ... <= pn）
（1）2 primes：
(p1 * p2) / (p1 * p2)
这样 p1 最小也只能是 3。（因为 2 不允许单开）。
那 p1*p2 最小只能 3*3 = 9。。。越界了。。。
所以不能是 2 primes。
待续。。。
【在 t*******r 的大作中提到】
: 证明没有其他相等稍微费些口舌，俺就这么简略的说吧。
: 首先这道题是连续整数 [ 3 ... 8 ]，为了凑那个 1
: (multiplicative identity)，这样根据 unique
: prime factorization （UPF) ，1 总是可以写成
: (p1 * p2 * p3 * ... * pn) / (p1 * p2 * p3 * ... * pn)
: 而对于楼上和楼下的 primes，搞不同的 association
: 而形成不重复的数字（显然上下至少要有一个 composite），
: 就形成一个 flippable pattern。。。另外一个限制条件
: 是 association 形成的这些数字必须落在 [ 3, 8 ] 之间。
: 待续。。。
|
t*******r
发帖数: 22634 | 24 (2) 3 primes:
(p1 * p2 * p3) / (p1 * p2 * p3)
(2.1) 首先不能搞 2 2 2，因为这样总会分出个 2 出来。
数字重复。
(2.2) 如果搞 2 p2 p3，p2 和 p3 都大于 2，那必然出
(2*p2*p3)，大于 8，统统越界。
(2.3) 如果没有 2，那最小的一种是 3 3 3，这样出 27
越界。次小的是 3 3 5，出 15 越界。剩下肯定都越界。
所以 3 primes 不行。
待续。
【在 t*******r 的大作中提到】
: 这题还有一个陷阱，就是 prime 2 已经出现，后面这个
: flippable pattern 不能出现 prime 2。。。不过这个
: 别阴沟翻船就好了。
: 然后按 prime 的数目递增开始凑：
: (为了方便起见，这里假设对 prime 排序，
: p1 <= p2 <= p3 <= ... <= pn）
: （1）2 primes：
: (p1 * p2) / (p1 * p2)
: 这样 p1 最小也只能是 3。（因为 2 不允许单开）。
: 那 p1*p2 最小只能 3*3 = 9。。。越界了。。。
|
t*******r
发帖数: 22634 | 25 （3）4 primes：
(p1 * p2 * p3 * p4) / (p1 * p2 * p3 * p4)
(3.1) 2 2 2 2，这玩意儿就不用费口舌了。
(3.2) 2 2 2 3, OK, we have 1 hit，形成：
((2 * 2) * (2 * 3)) / ((2 * 2 * 2) * 3)
=> (4 * 6) / (8 * 3)
(3.3) 2 2 2 p4, p4 >= 5, 不说了，越界。
待续。。。
【在 t*******r 的大作中提到】
: (2) 3 primes:
: (p1 * p2 * p3) / (p1 * p2 * p3)
: (2.1) 首先不能搞 2 2 2，因为这样总会分出个 2 出来。
: 数字重复。
: (2.2) 如果搞 2 p2 p3，p2 和 p3 都大于 2，那必然出
: (2*p2*p3)，大于 8，统统越界。
: (2.3) 如果没有 2，那最小的一种是 3 3 3，这样出 27
: 越界。次小的是 3 3 5，出 15 越界。剩下肯定都越界。
: 所以 3 primes 不行。
: 待续。
|
t*******r
发帖数: 22634 | 26 （4）5 primes, 6 primes ...
这个随便写写都越界了。。。主要是因为，8 / 2 = 4，
所以大于 4 的 prime 都不会在这个序列里，因为随便
找谁结婚都越界了哈哈哈。
【在 t*******r 的大作中提到】
: （3）4 primes：
: (p1 * p2 * p3 * p4) / (p1 * p2 * p3 * p4)
: (3.1) 2 2 2 2，这玩意儿就不用费口舌了。
: (3.2) 2 2 2 3, OK, we have 1 hit，形成：
: ((2 * 2) * (2 * 3)) / ((2 * 2 * 2) * 3)
: => (4 * 6) / (8 * 3)
: (3.3) 2 2 2 p4, p4 >= 5, 不说了，越界。
: 待续。。。
|
t*******r
发帖数: 22634 | 27 但这么一来，这种 primes 的问题如此之不连续，搞到 80 甚至 N
的话，多半要马 code 电算才靠谱，肉算累都累趴下了。。。
但这样一来又麻烦了，我前面那么多条规则，写成电算那马 code
的行数也给马趴下了。。。
不过不急嘛，马工们有大杀器。。。
待续。。。
【在 t*******r 的大作中提到】
: （4）5 primes, 6 primes ...
: 这个随便写写都越界了。。。主要是因为，8 / 2 = 4，
: 所以大于 4 的 prime 都不会在这个序列里，因为随便
: 找谁结婚都越界了哈哈哈。
|
p**s
发帖数: 2707 | 28 80我就随手一写。。。估计你得上code
【在 t*******r 的大作中提到】
: 但这么一来，这种 primes 的问题如此之不连续，搞到 80 甚至 N
: 的话，多半要马 code 电算才靠谱，肉算累都累趴下了。。。
: 但这样一来又麻烦了，我前面那么多条规则，写成电算那马 code
: 的行数也给马趴下了。。。
: 不过不急嘛，马工们有大杀器。。。
: 待续。。。
|
t*******r
发帖数: 22634 | 29 好吧，马工这个大杀器有个大名词叫 (prime) factor lattices
http://www.mathrecreation.com/2008/09/factor-lattices.html
其实也不一定用那个 lattice 结构，可能也有其他的 lattice 结构
更方便。。。总而言之把这个问题，转化为高维拓扑空间的拓扑问题，
然后切个边界，数一数，就可以走人了。。。
当然，骨灰级数学家们可能有更刁钻的办法。。。但马工们一天那么多
事儿也来不及刁钻。。。反正更刁钻的办法一般也快不了多少了，
而且碰到实际问题再加几个限制条件的话，骨灰级数学家的刁钻
办法搞不好也会爆掉。。。其实最关键的，主要还是英特尔的芯片
也没几个钱，达特茅斯地下室写 JavaScript 的炮灰们也没几个钱
。。。所以剩下的具体马 code 的事儿，让月光啥的随便写个
JavaScript 出货就完事了。。。
【在 t*******r 的大作中提到】
: 但这么一来，这种 primes 的问题如此之不连续，搞到 80 甚至 N
: 的话，多半要马 code 电算才靠谱，肉算累都累趴下了。。。
: 但这样一来又麻烦了，我前面那么多条规则，写成电算那马 code
: 的行数也给马趴下了。。。
: 不过不急嘛，马工们有大杀器。。。
: 待续。。。
|
t*******r
发帖数: 22634 | 30 我当中跳掉几个数切掉一小块，你估计就不能随手一写了。。。
很多 paper 工业界没法用，其实就是因为当中跳掉一小块。。。
【在 p**s 的大作中提到】
: 80我就随手一写。。。估计你得上code
|
|
|
p**s
发帖数: 2707 | 31 我是说80这个数是我随手一写，不是说结果我能随手一写。。。
【在 t*******r 的大作中提到】
: 我当中跳掉几个数切掉一小块，你估计就不能随手一写了。。。
: 很多 paper 工业界没法用，其实就是因为当中跳掉一小块。。。
|
t*******r
发帖数: 22634 | 32 另外一个思路，是用分数约到最简，所有相同的 prime 被消去，
这样就不用先计算再去掉重复，只要计算能出现多少 prime
的组合。。。这个好像更简单。。。 |
t*******r
发帖数: 22634 | 33 真可能还有更好的方法，不一定。。。我上面有个新思路。。。
也就是说，把每个 composite 都分解变成 prime，然后
每个 composite 里面的所有 prime 要一起走，要么统统在上面，
要么统统在下面，根据 unique prime factorization，
这样变成数分子上下的 prime 出现多少次的问题。。。因为
composite 里面的 prime 要一起动，也就是 permutation
under constraints 的问题，这样建模成一个 combinatronics
问题。。。搞不好真有可能随手一写个排列组合公式。。。
也就是说
(2^(a1) * 3^(a2) * 5^(a3) * ...) / (2^(b1) * 3^(b2) * 5^(b3) * ...)
变成 c1, c2, c3, c4 是整数（可以非负）。
2^(c1) * 3^(c2) * 5^(c3) * ....
那根据 unique prime factorization 和 fraction 的理论，每一个
c1, c2, c3，... 序列一一对应一个数值。。。所以这个就变成
计算有多少 unique 的 c1, c2, c3, ... 序列的问题。
说不定可行。。。等俺想想。。。
【在 p**s 的大作中提到】
: 我是说80这个数是我随手一写，不是说结果我能随手一写。。。
|
p**s
发帖数: 2707 | 34 不行，比如2的都在上面，6就要在上面，3就不可以都在下面
【在 t*******r 的大作中提到】
: 真可能还有更好的方法，不一定。。。我上面有个新思路。。。
: 也就是说，把每个 composite 都分解变成 prime，然后
: 每个 composite 里面的所有 prime 要一起走，要么统统在上面，
: 要么统统在下面，根据 unique prime factorization，
: 这样变成数分子上下的 prime 出现多少次的问题。。。因为
: composite 里面的 prime 要一起动，也就是 permutation
: under constraints 的问题，这样建模成一个 combinatronics
: 问题。。。搞不好真有可能随手一写个排列组合公式。。。
: 也就是说
: (2^(a1) * 3^(a2) * 5^(a3) * ...) / (2^(b1) * 3^(b2) * 5^(b3) * ...)
|
t*******r
发帖数: 22634 | 35 但这里有个不正交的问题，比如一个 6，prime 是 2 和 3，
那要么是 2^1 和 3^1，要么是 2^(-1) 和 3^(-1)，这两玩意儿
联动的问题要解决。
这个可能用 constrained bi-partition algorithm 可能可以
解决，时空复杂性和代码复杂度可能比我前面的对付 8 的办法
来得好。。。有时候，规模的变化可能导致算法的质变。。。
【在 t*******r 的大作中提到】
: 真可能还有更好的方法，不一定。。。我上面有个新思路。。。
: 也就是说，把每个 composite 都分解变成 prime，然后
: 每个 composite 里面的所有 prime 要一起走，要么统统在上面，
: 要么统统在下面，根据 unique prime factorization，
: 这样变成数分子上下的 prime 出现多少次的问题。。。因为
: composite 里面的 prime 要一起动，也就是 permutation
: under constraints 的问题，这样建模成一个 combinatronics
: 问题。。。搞不好真有可能随手一写个排列组合公式。。。
: 也就是说
: (2^(a1) * 3^(a2) * 5^(a3) * ...) / (2^(b1) * 3^(b2) * 5^(b3) * ...)
|
t*******r
发帖数: 22634 | 36 是这个问题，要解决这个非正交的联动问题。。。对于 8 铁定不划算，
但对于 80 或者更大的数字来说，这个 direct solve 的办法，比起
前面那个 factor lattice 的方法，不一定差，要比较才知道。。。
我觉得可以试试用 constructive bi-partition algorithm 的想法，
把所有联动的都构成一个一个 set，然后用 constructive graph
algorithm 那一类算法求解。。。
而且最大的好处，是这个可以对付不连续数字的情况，在工业界类似
问题多半更实用。
【在 p**s 的大作中提到】
: 不行，比如2的都在上面，6就要在上面，3就不可以都在下面
|
t*******r
发帖数: 22634 | 37 等俺先把正事干完，老板喊俺回 cube 马 code 中。。。 |
t*******r
发帖数: 22634 | 38 这两个可能可以结合起来。。。对电算有利，但是肉算写下来可能比较
麻烦，我就大概写一写。
先解对于 8 的问题。。。首先我建模写成一个 list，该 list 的每一个项
是一个 sub-list，对应于该位置的每个 prime 所可能出现的指数值。
prime 按 { 2 3 5 7 } 来排序。
那么如果用 greedy constructive algorithm 的话，先填入所有
的 prime 3 5 7，这样就变成：
{ {0}, {-1, 1}, {-1, 1}, {-1, 1} }
然后填入非联动的 composite 4 和 8，这样变成：
{ {-5, -1, 1, 5}, {-1, 1}, {-1, 1}, {-1, 1} }
然后填入联动的 composite 6，这样 decision tree 就分叉
成两个情况。。。text 不太好画，我就意思意思用 same
as above 代表公共 parent 节点：
{ {-4, 0, 2, 6}, {0, 2}, {-1, 1}, {-1, 1} }
{ {-6, -2, 0, 4}, {-2, 0}, }
由于前面两个的 partial list 存在交集 { {0}, {0} }，
（其实不是严格的 tree 的，叶子存在交集，但是建模
和数据结构无所谓，只要表达清楚就行）。所以扣掉重复就是：
(4*2*2 - 1)*2*2 = 60 种不同的数值。 |
d****g
发帖数: 7460 | 39 我怎么算成个21..
Fn = F n-1 + F n-2 |
t*******r
发帖数: 22634 | 40 你这个数学归纳法也给写出来啊，否则人猜不出你啥想法。。。
【在 d****g 的大作中提到】
: 我怎么算成个21..
: Fn = F n-1 + F n-2
|
|
|
p**s
发帖数: 2707 | 41 他想的是
(1/2)/.....
和1/(2/....)
【在 t*******r 的大作中提到】
: 你这个数学归纳法也给写出来啊，否则人猜不出你啥想法。。。
|
t*******r
发帖数: 22634 | 42 这个是 F(n)= 2*F(n-1) ？如果不考虑等值的出现。。。
【在 p**s 的大作中提到】
: 他想的是
: (1/2)/.....
: 和1/(2/....)
|
t*******r
发帖数: 22634 | 43 漏了说明一下所有情况都能出现。。。其实就是存在一种加括号的方式，使得任意上蹿
下跳组合都出现。。。这么说，只加左括号，每一位可以选择加或者不加。。。如果加
了，那后面所有的都 flip phase，否则啥都不变，这么从左到右一个一个过去，到底
后才用右括号们全部 close 掉。。。这样的加括号方式，可以保证所有上窜下跳的组
合都出现。。。所以是 permutation w/ repetition (对 phase 而言)。
【在 t*******r 的大作中提到】
: 不管如何加括号，最后化成一个长分数的话，从 3 开始(包括 3)，每个数要么是在分
: 子上，要么是在在分母上。(或者好比电路的 pos phase vs neg phase)。
: 这样首先就是 permutation w/ repetition 的问题，如果先不管相同值的重复，那就
: 是有 2^6 种 permutation。
: 下面算重复，prime 不会导致出重复，重复是由 composite 造成的。
: 俺得先开会去。。。回来再搞。。。
|
p**s
发帖数: 2707 | 44 这个是很重要
【在 t*******r 的大作中提到】
: 漏了说明一下所有情况都能出现。。。其实就是存在一种加括号的方式，使得任意上蹿
: 下跳组合都出现。。。这么说，只加左括号，每一位可以选择加或者不加。。。如果加
: 了，那后面所有的都 flip phase，否则啥都不变，这么从左到右一个一个过去，到底
: 后才用右括号们全部 close 掉。。。这样的加括号方式，可以保证所有上窜下跳的组
: 合都出现。。。所以是 permutation w/ repetition (对 phase 而言)。
|
d****g
发帖数: 7460 | 45 我这看了答案再凑打了折扣。。。
前头算错是光算了1(2345678) 和(1234567)8
现在想来，是除了2，你都能整到分子来。。。所以 135 分子，24678分亩。。。137分
子，则24568分母。
分子的选择为 64种。
但 3*8=4*6
所以 1 5 7 算重。 1 ， 15， 17 157 。。需要减4。
是为60.
---
又爬了楼，，，原来大家早想明白了。。这题小学也太难了吧。。 |
