小练习：20160822 找出具有一种奇怪约分性质的所有分数

冬雪雪冬 · 发表于 2016-8-21 21:48:34

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由冬雪雪冬于 2016-8-29 10:04 编辑

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了81道题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives
这里已经有了500余题。

登录/注册后可看大图

好了言归正传，我们开始做小练习。

题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
题目比较简单，注重程序效率和创意。
答题在一周内完成，即8.29 10：00之前，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。

----除列出程序外，请给出输出的结果。----

题目：

分数 49/98 是一个奇怪的分数：当一个菜鸟数学家试图对其进行简化时，他可能会错误地可以认为通过将分子和分母上的

9 同时去除得到 49/98 = 4/8。但他得到的结果却是正确的。

我们将 30/50 = 3/5 这样的分数作为普通个例。

一共有四个这样的非普通分数，其值小于 1，并且包括分子和分母都包括 2 位数。

如果将这四个分数的乘积约分到最简式，分母是多少？

冬雪雪冬 · 发表于 2016-8-21 21:50:31

本题用python自带的分数类型很方便。
结果是100。

from fractions import Fraction
product = 1
for i1 in range(1, 10):
for i2 in range(0, 10):
for j in range(1, 10):
frac = Fraction(i1 * 10 + i2, i2 * 10 + j)
if frac < 1 and frac == Fraction(i1, j):
product *= frac
print(product.denominator)

复制代码

过河的小卒 · 发表于 2016-8-22 11:02:56

本帖最后由过河的小卒于 2016-8-22 11:07 编辑

list1 = []
fenzi = 1
fenmu = 1
for i in range(12,99):
for j in range(11,i):
if len(set(str(i)+str(j))) < 4 and i%10 != 0 and j%10 != 0 :
i1 = i%10
i2 = i//10
j1 = j%10
j2 = j//10
if i1 == j1:
if j/i == j2/i2:
list1.append((j,i))
fenzi = fenzi*j2
fenmu = fenmu*i2
if i1 == j2:
if j/i == j1/i2:
list1.append((j,i))
fenzi = fenzi*j1
fenmu = fenmu*i2
if i2 == j1:
if j/i == j2/i1:
list1.append((j,i))
fenzi = fenzi*j2
fenmu = fenmu*i1
if i2 == j2:
if j/i == j1/i1:
list1.append((j,i))
fenzi = fenzi*j1
fenmu = fenmu*i1
print(list1)
print(str(fenzi)+'/'+str(fenmu))

复制代码

输出：
[(16, 64), (26, 65), (19, 95), (49, 98)]
8/800
约分函数懒得写了，答案因该是100

bacon6581 · 发表于 2016-8-22 11:39:50

from time import time
start=time()
x=1
y=1
#i/j,m/n
j=10
#穷举法，j从11举到99（两位数，且j要比i大）
while j<100:
j+=1
i=9
#i从10举到j-1(两位数，分子要比分母小，这个分数才会比1小)
while i<j-1:
m=99
n=99
i+=1
#如果分子的十位跟分母的十位相同，那么m为分子的个位数、n为分母的个位数
if int(i/10) == int(j/10):
m=i-int(i/10)*10
n=j-int(j/10)*10
#如果分子的个位跟分母的十位相同，那么m为分子的十位数、n为分母的个位数
elif i-int(i/10)*10 == int(j/10):
m=int(i/10)
n=j-int(j/10)*10
#下边两个判断原理同上
elif int(i/10) == j-int(j/10)*10:
m=i-int(i/10)*10
n=int(j/10)
elif i-int(i/10)*10 == j-int(j/10)*10:
m=int(i/10)
n=int(j/10)
#如果m<10即上面的四个判断必有一个成立，分子分母里有数字相同，且已舍去
#j如能被10整除，则属于普通个例，排除掉
#m/n==i/j成立，把m和n的值记下
if m<10 and j/10!=int(j/10) and m/n==i/j:
x=m*x
y=n*y
#分数化到最简，莫过于分子为1，即分母除于分子，且能被整除时
#这里偷了懒，我是先求出四个分数后（1/4，2/5，1/5，1/2），一看2和2刚好能约掉，就直接除吧
print(int(y/x))
print(time()-start)

复制代码

>>> ================================ RESTART ================================
>>>
100
0.15532398223876953
>>>

复制代码

老忘 · 发表于 2016-8-23 10:59:52

# -*- coding:Utf-8 -*-
import time
start = time.clock()
def check(i,j):
if i*int(str(j)[0])==j*int(str(i)[1]) and str(j)[1]==str(i)[0]:
return 1
else:
return 0
def gcd(a, b):
"""通过辗转相除法取最大公因数"""
if a < b:
a, b = b, a
y = a % b
if y == 0:
return b
else:
a, b = b, y
return gcd(a,b)
list_soure=[]
fz=1
fm=1
for i in range(10,100):
list_soure.append(i)
for i in range(1,len(list_soure)):
for j in range(0,i):
if check(list_soure[i],list_soure[j]):
fz=fz*list_soure[j]
fm=fm*list_soure[i]
print(int(fm/gcd(fz,fm)))
end = time.clock()
print ("read: %f s" % (end - start))

复制代码

计算结果：

100

复制代码

飘飞的白杨 · 发表于 2016-8-23 18:57:04

import math
l = []
for i in range(1, 10):
for j in range(i+1, 10):
for k in range(2, 100):
if i*k%10 == 0 and i*k//10 == 0 and j*k%10 == 0 and j*k//10 == 0:
continue
if (i*k%10 == j*k//10 and i*k//10*j == j*k%10*i) or (i*k//10 == j*k%10 and i*k%10*j == j*k//10*i):
if [i*k,j*k] not in l:
l.append([i*k,j*k])
print(l[0][1]*l[1][1]*l[2][1]*l[3][1]//math.gcd(l[0][0]*l[1][0]*l[2][0]*l[3][0],l[0][1]*l[1][1]*l[2][1]*l[3][1]))

复制代码

答案：100

无下限HENTAI · 发表于 2016-8-24 16:22:20

import time as t
from fractions import Fraction as F
start = t.time()
def solution():
result = []
for i in range(11,79):
for j in range(21,99):
if i%10 != 0 and j%10 != 0 and j-i>10:
a = str(i)
b = str(j)
if a[0] == b[1]:
c = F(int(a[1]),int(b[0]))
if c == F(i,j):
result.append(c)
print('%s/%s'%(a,b),end = '\t')
elif a[1] == b[0]:
c = F(int(a[0]),int(b[1]))
if c == F(i,j):
result.append(c)
print('%s/%s'%(a,b),end = '\t')
elif a[1] == b[1]:
c = F(int(a[0]),int(b[0]))
if c == F(i,j):
result.append(c)
print('%s/%s'%(a,b),end = '\t')
product = 1
for k in result:
product *= k
print('\n乘积是：%s'%str(product))
print('最简分母是：%d'%product.denominator)
solution()
print('用时%.5f秒'%(t.time()-start))

复制代码

结果：
16/64 19/95 26/65 49/98
乘积是：1/100
最简分母是：100
用时0.04688秒

wy6616753 · 发表于 2016-8-26 19:40:04

sum1 = 1
sum2 = 1
for a in range(10, 99):
for b in range(a+1, 100):
      if b/a == (b%10)/(a//10):
         sum1 *= a
         sum2 *= b

x = sum2
while sum2 != 0:
temp = sum1 % sum2
sum1 = sum2
sum2 = temp

print(x/sum1)

wangzhenas · 发表于 2016-8-28 05:16:02

答案：100
思路：满足题设分数满足如下形式：
i/j = (i*10+k)/(k*10+j)
通过列表推倒式得到满足条件的分数
在通过reduce方法求出积
最后通过while方法约分即可求出分母

from time import time as t
from functools import reduce
t0,n = t(),2
l = reduce(lambda i,j: [i[0]*j[0],i[1]*j[1]],[[i,j] for i in range(10) for j in range(i+1,10) for k in range(1,10) if i*(k*10+j) == j*(i*10 + k)])
while n <= l[0]:
if l[0] % n == 0 and l[1] % n == 0:
l[0],l[1] = l[0]//n,l[1]//n
else:
n += 1
print(l[1],t()-t0)

复制代码

mather · 发表于 2016-8-28 21:46:16

fenzi = 1
fenmu = 1
for i in range(11,100):
for j in range(i+1,100):
if i%10==0 or j%10 ==0:
continue
temp1 = list(str(i))
temp2 = list(str(j))
allin = [x for x in temp1 if x in temp2]
if len(allin)!=1:
continue
temp1.remove(allin[0])
temp2.remove(allin[0])
if i/j == (int(temp1[0])/int(temp2[0])):
fenzi = fenzi * i
fenmu = fenmu * j
print(fenzi/fenmu)
from fractions import Fraction
Fraction(fenzi,fenmu)

复制代码

输出结果：0.01
化为分式：1/100
所以结果是：100

账号		自动登录	找回密码
密码			立即注册

[技术交流] 小练习：20160822 找出具有一种奇怪约分性质的所有分数

马上注册，结交更多好友，享用更多功能^_^

本帖被以下淘专辑推荐:

评分

评分

评分

评分

评分

评分

评分