小练习：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))

计算结果：

飘飞的白杨 · 发表于 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 找出具有一种奇怪约分性质的所有分数

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

本帖被以下淘专辑推荐:

评分

评分

评分

评分

评分

评分

评分