#用数字 1 到 8 组成两个三位数使其和为 1000,这两个三位数里面的数字不能重复。
#问能写几组?
#用小学三年级的解题思路还真没想到。
#只好用笨方法跑个小程序了。
L=list(range(1,9))
#print(L)
s=""
S=[]
for l in L:
for l1 in L:
for l2 in L:
if str(l)<>str(l1) and str(l)<>str(l2) and str(l1)<>str(l2):
s=str(l) + str(l1) + str(l2)
S.append(s)
def IsSame(a,b):
v=True
for al in a:
for bl in b:
if al==bl:
v= False
return v
C1000=[]
for c in S:
v=1000-int(c)
if str(v)[0]<>str(v)[1] and str(v)[0]<>str(v)[2] and str(v)[1]<>str(v)[2] and str(v)[2]<>'9' and IsSame(c,str(v)):
C1000.append(c)
#print(C1000)
#print(len(C1000))
n=1
DisplayList=[]
for i in range(len(C1000)/2):
DisplayList.append(C1000[i] + " + " + C1000[len(C1000)-n] + " = 1000")
n+=1
print(DisplayList)
最终结果有 24 组:
'124 + 876 = 1000', '126 + 874 = 1000',
'143 + 857 = 1000', '147 + 853 = 1000',
'153 + 847 = 1000', '157 + 843 = 1000',
'174 + 826 = 1000', '176 + 824 = 1000',
'214 + 786 = 1000', '216 + 784 = 1000',
'284 + 716 = 1000', '286 + 714 = 1000',
'342 + 658 = 1000', '348 + 652 = 1000',
'352 + 648 = 1000', '358 + 642 = 1000',
'413 + 587 = 1000', '417 + 583 = 1000',
'432 + 568 = 1000', '438 + 562 = 1000',
'462 + 538 = 1000', '468 + 532 = 1000',
'483 + 517 = 1000', '487 + 513 = 1000'
1
ynyounuo 2017-10-07 02:17:43 +08:00 via iPhone 4
不要太简单
1/9 2/8 3/7 4/6 个位和十位的组合 1/8 2/7 3/6 4/5 百位的组合 加法交换律所以组合数量翻倍 8 * 3 = 24 |
4
casparchen 2017-10-07 02:59:18 +08:00
l = ["%d+%d=1000"%(x,1000-x) for x in range(100,999) if len(set(str(x)+str(1000-x)))==6 and '0' not in str(x)+str(1000-x) and '9' not in str(x)+str(1000-x)]
print(l) |
5
casparchen 2017-10-07 03:51:15 +08:00 1
l = ["%d+%d=1000"%(x,1000-x) for x in range(100,500) if len(set(str(x)+str(1000-x)).intersection(list('12345678'))) == 6]
|
6
Valyrian 2017-10-07 04:47:36 +08:00 via iPhone
个位 4 个选择,选完后十位三个选择,都选完后个位两个选择
|
7
athanos 2017-10-07 04:54:41 +08:00 via Android
这种数位题的要点就是进位只可能是进 1 或 0。
|
8
Xs0ul 2017-10-07 05:17:43 +08:00
“难度”在于,可能的结果太多,导致除了穷举凑 9、10 和去除重复以外,没什么合理的、靠推理的算法。而穷举,人和计算机的逻辑方式没什么差别,只是体力活。
还是那种竖式填空的比较有趣( |
9
vegito2002 2017-10-07 05:53:16 +08:00 4
我个人认为这个题目推理其实并不难想, 以下推理过程虽然话比较多, 不过纯粹是为了表达的严谨, 事实上整个问题思路非常简单.
考虑这四个 pair: [0]: 1 8 [1]: 2 7 [2]: 3 6 [3]: 4 5 我们命名为 pair[0] ~ pair[3] 比较简单的一个事实就是, 而我们要选择的是三个 digit, digit[0] ~ digit[2], 对应个位到百位; digit[1], digit[2]都是比较简单的, 只要找到两个相加等于 9 的就行了, 事实上, 这两个 digit 上面的位置, 只要在上面 pair[0]..[3]当中选择一个就行了; 但是 digit[0]呢? 事实上, digit[0]我们需要两个 pair, 而且要两个相邻的 pair, 这是因为每一个 pair 的和是 9, 而 digit[0]需要做到的和是 10. 所以 digit[0]最后实际上要找到的就是一个 pair[i], 然后一个 pair[i+1], 然后用 pair[i][0] and pair[i-1][1]组成的一个 pair 就行了; 所以我们最后要找到两个相邻的 pair, 然后取这两个 pair 的类似于一个对角线的就行了; 注意, 当 digit[0]选择了两个 pair 之后, 这两个 pair 就无法再参与到其他 digit 的组合当中了: 这是因为剩下的 pair[i][1]只能和 pair[i][0]组合得到 9, 而 pair[i-1][0]只能和 pair[i-1][1]组合得到 9, 但是这两个姘头都已经被作为对角线拿到 digit[0]的制造当中去了; 所以最后问题简化下来就是, 先选两个相邻 digit, 找到对角线(注意, 虽然有两条对角线, 但是只有一种选择方法能够得到 10, 另一个得到的是 8), 这个有 3 中选法; 剩下的两个 pair, 就是参与到 digit[1] and digit[2]的制造当中, 因为是二对二, 所以没有选择问题了, 但是有一个排序问题, 因为你不知道谁给 digit[1], 谁给 digit[2], 所以这里有一个 2!. 然后 digit[1]和 digit[2]分别得到自己的 pair 之后, 内部还要排序, 所以是 2! * 2!. 这里有一个问题, digit[0]内部是否需要继续排序? 答案是不需要, 因为 digit[1] and digit[2]都已经排序过了, 你如果 digit[0]还重新排序, 或者说交换顺序, 最后得到的就肯定有重复; 所以最后得到的答案就是 3 * 2! * (2! * 2!); 注意最后两个 2!的含义跟第一个 2!的含义的区别, 一个是 digit 之间排序, 一个是 digit 内部排序导致的; 我不认为这个问题很弱智, 我感觉了 LeetCode 里面若干题目涉及到的数学其实也就差不多这个水平. |
10
vegito2002 2017-10-07 06:48:35 +08:00
上面第三段第一句话有一个地方打错了的:
所以最后问题简化下来就是, 先选两个相邻 **pair**, 找到对角线(注意, 虽然有两条对角线, 但是只有一种选择方法能够得到 10, 另一个得到的是 8), 这个有 3 中选法; |
11
supman 2017-10-07 09:07:19 +08:00 via Android
有没有完全不会做的?比如我
|
12
a1044634486 2017-10-07 09:40:14 +08:00
@supman 回去上学吧。
|
13
glouhao 2017-10-07 09:48:41 +08:00 via Android
出这个题有啥目的呢 能启发小孩子什么 a4 纸太小?我们要用超级大本子?
|
14
est 2017-10-07 09:52:59 +08:00
没人写个 minikanren 版本?
|
16
royrs 2017-10-07 10:11:32 +08:00 via iPhone 1
可以这样考虑呀;
满足要求的两个三位数,其个位相加和为 10 ;十位相加和为 9,百位相加和为 9。 然后分为如下两组因子,一组因子是 1-8 中,相加和为 10 的因子,如下: (2,8),(3,7),(4,6) 然后另一组和为 9 的因子,如下: (1,8),(2,7),(3,6),(4,5) 于是我们如果要组成两个三位数,只需要从 10 因子组中取 1 个因子,9 因子中取两个因子就可以。 但是要考虑,取 10 因子中的一组后,9 因子中包含 10 因子组的数字的因子应该被屏蔽掉,同时考虑十位百位的轮换性即可。 于是这样的组合就有: 3*2*2*2=24 种 这样算感觉最多半面 A4 纸能列举完? (╯°□°)╯︵ ┻━┻ |
17
sunine 2017-10-07 10:25:57 +08:00 4
来个小学生版的
|
18
luofeii 2017-10-07 10:29:39 +08:00 via Android
个位只有三种选择
2-8 3-7 4-6 十位和百位只有四种选择 1-8 2-7 3-6 4-5 以个位选择 2-8 为例 十位的选择有两种 1-8 否 有 8 2-7 否 有 2 3-6 4-5 十位和百位的两种选择进行排练组合 有十位 3-6 对应百位 4-5 有 4 种组合 十位百位反之同样有 4 种组合 共有 3x ( 4x2 )种组合 |
20
loongwang 2017-10-07 10:46:21 +08:00
/**
#用数字 1 到 8 组成两个三位数使其和为 1000,这两个三位数里面的数字不能重复。 #问能写几组? */ public class OneThousand { static boolean []v=new boolean[9]; public static int robot(int idx,int x,int y){ if(idx==0) return 1; int ans=0; for(int i=1;i<=8;i++){ if(v[i]==false&&v[9-i]==false){ v[i]=true; v[9-i]=true; ans+=robot(idx-1,i,9-i); v[i]=false; v[9-i]=false; } } return ans; } public static void main(String[] args){ int sum=0; //个位,防止重复 for(int i=2;i<5;i++){ v[i]=true; v[10-i]=true; sum+=robot(2,i,10-i); v[i]=false; v[10-i]=false; } System.out.print(sum); } } 回溯法,两个数的个位相加必为 0,非个位相加必为 9(因为有之前的进位) |
21
larsenlouis 2017-10-07 11:51:06 +08:00
更短的笨方法
``` from itertools import combinations, permutations pick_6_numbers = combinations(range(1,8+1), 6) index_mappings = list(permutations(range(6), 6)) num1_set = set() count = 0 for picked in pick_6_numbers: for a,b,c,d,e,f in index_mappings: num1 = 100 * picked[a] + 10 * picked[b] + picked[c] num2 = 100 * picked[d] + 10 * picked[e] + picked[f] if num1 + num2 == 1000: num1_set.add(num1) if num2 not in num1_set: count += 1 print('{} + {} = 1000'.format(num1, num2)) print('total: {}'.format(count)) ``` |
22
liuminghao233 2017-10-07 13:24:27 +08:00 via iPhone
卧槽写出其中一组还算正常
问能写几组就有点过分了 |
24
Telegram 2017-10-08 00:07:31 +08:00
@liuminghao233 #22 对,现在小学生的题目感觉都是大题。
|
25
sevenknights 2017-10-09 10:22:59 +08:00
/*有推理的功夫直接穷举得了*/
main(a, c, s){ for(char r[32]; sprintf(r, "%d + %d", a, 1000 - a) && a++ < 500;) for(s = 0, c = '1'; c < '9'; ++c) if((s += !!strchr(r, c)) == 6) printf("%s = 1000 \n", r); } |