题目33：找出具有一种奇怪约分性质的所有分数

欧拉计划 · 发表于 2015-4-23 23:43:37

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

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

x

本帖最后由欧拉计划于 2015-4-23 23:45 编辑

Digit cancelling fractions

The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, 30/50 = 3/5, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

题目：

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

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

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

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

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

迷雾少年 · 发表于 2016-8-29 17:03:18

本帖最后由迷雾少年于 2016-8-29 17:07 编辑

16/64
26/65
49/98
19/95

/输入2个数字去除相同的数字返回相除结果
float calc2(int a,int b)
{
float a1 = a%10; //a的个位数
float a2 = (a/10)%10; //a的十位数
float b1 = b%10; //b的个位数
float b2 = (b/10)%10; //b的十位数
if(a1==b1) return a2/b2;
else if(a1==b2)
{
return a2/b1;
}
else if(a2==b1)return a1/b2;
return 0;
}
int main()
{
for (float fenmu=1;fenmu<100;fenmu++)
{
for (float fenzi=1;fenzi<fenmu;fenzi++)
{
if(calc2(fenzi,fenmu) == fenzi/fenmu )
{
cout<<fenzi<<"/"<<fenmu<<endl;
}
}
}
return 0;
}

复制代码

愤怒的大头菇 · 发表于 2016-9-2 16:37:52

list1 = []
count_i=1
count_j=1
for i in range(10,100):
for j in range(10,100):
if i < j:
str_1 = str(i)
if str_1[0]!=str_1[1] and str_1[1]!='0':
for each in str(i):
if each in str(j):
temp = int(str(i).replace(each,'',1))
tmp = int(str(j).replace(each,'',1))
if (tmp!=0) and (temp/tmp == i/j) :
count_i *=i
count_j *=j
list2 = []
def gcd(x,y):
if y:
return gcd(y,x%y)
else:
return x
x = gcd(count_i,count_j)
print(int(count_j/x))

复制代码

结果是100

芒果加黄桃 · 发表于 2017-1-13 22:03:16

# encoding:utf-8
# pandigital 之和
from time import time
def isUc(m, n):
if len(str(m).strip(str(n))) == len(str(m)):
return False
m1 = str(m).strip(str(n))
n1 = str(n).strip(str(m))
if not m1 or not n1:
return False
if int(m1) / int(n1) == m / n:
return True
return False
def euler033():
l_result = []
for i in range(11, 100):
if i % 10 == 0 or i % 11 == 0:
continue
for j in range(11, i):
if j % 10 == 0 or j % 11 == 0:
continue
if isUc(j, i):
print(i, j)
l_result.append(i)
print(sum(l_result))
if __name__ == '__main__':
start = time()
euler033()
print('cost %.6f sec' % (time() - start))

复制代码

64 16
65 26
95 19
98 49
322
cost 0.006003 sec

渡风 · 发表于 2017-6-5 00:47:38

此代码使用matlab编程
Problem33所用时间为1.2507秒
Problem33的答案为100

% Problem33.m
% 最后编辑时间：17-06-05 0:18
% 问题：求所有非正常约分的分数的乘积的分母
tic
Up = 1;
Down = 1;
for aa = 99 : -1 : 12
Deno = aa;
for bb = Deno - 1: -1: 11
Elem = bb;
NewDeno = num2str(Deno);
OtherDeno = str2double(NewDeno(2));
NewElem = num2str(Elem);
OtherElem = str2double(NewElem(1));
if OtherElem / OtherDeno == Elem / Deno ...
&& strcmp(NewDeno(1),NewDeno(2)) == 0 && strcmp(NewElem(1),NewElem(2)) == 0 && strcmp(NewDeno(1),NewElem(2)) == 1
Up = Up * Elem;
Down = Down *Deno;
end
end
end
Gcd = gcd(Up,Down);
Output = Down / Gcd;
toc
disp('此代码使用matlab编程')
disp(['Problem33所用时间为',num2str(toc),'秒'])
disp(['Problem33的答案为',num2str(Output)])

复制代码

匿名鱼油 *发表于 2018-4-17 22:32:19* · 发表于 2018-4-17 22:32:19

迷雾少年发表于 2016-8-29 17:03
16/64
26/65
49/98

去除普通个例

Trami · 发表于 2018-9-10 20:06:02

本帖最后由永恒的蓝色梦想于 2020-7-2 18:34 编辑

c = []
for i in range(10, 100):
c.append(i)
d = []
for i in range(10, 100):
d.append(i)
a = []
for item in c:
# print(item)
for item1 in str(item):
a.append(item1) # 最新的数据都是-1,-2
b = []
for item in d:
# print(item)
for item1 in str(item):
b.append(item1)
for i in range(0, 180, 2):
for j in range(0, 180, 2):
A = int(a[i])
B = int(a[i + 1])
C = int(b[j])
D = int(b[j+1])
if D == 0 or C == 0:
continue
if (A*10 + B) != (C*10 + D):
if A == D:
if (A*10 + B) / ((C*10 + D)*1.0) == B/(C*1.0):
print((A*10 + B), (C*10 + D))
print('-------1-------')
if A == C:
if (A*10 + B) / ((C*10 + D)*1.0) == B/(D*1.0):
print((A*10 + B), (C*10 + D))
print('-------2-------')
if B == C:
if (A*10 + B) / ((C*10 + D)*1.0) == A/(D*1.0):
print((A*10 + B), (C*10 + D))
print('-------3-------')
if B == D:
if (A*10 + B)/((C*10 + D)*1.0) == A/(C*1.0):
print((A*10 + B), (C*10 + D))
print('-------4-------')

复制代码

k往事如烟k · 发表于 2019-3-26 16:20:33

['16/64', '19/95', '26/65', '49/98']
322
cost 0.000000 sec

from time import time
def EP033():
list1 = []
for a in range(10, 100):
for b in range(a + 1, 100):
if (a // 10 == b // 10 or a // 10 == b % 10 or a % 10 == b // 10 or a % 10 == b % 10) and (
a % 10 != 0 and b % 10 != 0):
list1.append(str(a // 10) + str(a % 10) + "/" + str(b // 10) + str(b % 10))
list2 = []
for each in list1:
if each[0] == each[3]:
list2.append(each[1:3] + each[4])
elif each[0] == each[4]:
list2.append(each[1:4])
elif each[1] == each[3]:
list2.append(each[0] + each[4])
else:
list2.append(each[0] + each[3])
value_list1 = []
value_list2 = []
for each1 in list1:
value_list1.append(round(int(each1[:2]) / int(each1[3:]), 3))
for each2 in list2:
value_list2.append(round(int(each2[0]) / int(each2[-1]), 3))
list3 = []
for i in range(len(list1)):
if value_list1[i] == value_list2[i]:
list3.append(list1[i])
print(list3)
sum = 0
for each3 in list3:
sum += int(each3[3:])
print(sum)
if __name__ == '__main__':
start = time()
EP033()
print('cost %.6f sec' % (time() - start)

复制代码

王小召 · 发表于 2019-6-13 13:11:52

分子分母：[(49, 98), (19, 95), (16, 64), (26, 65)]
化简分母：[100.0]
用时：0.156001秒

import functools
import time
def get_strange_list():
result = []
s_list = []
# x > y
for x in range(11, 100):
for y in range(11, x):
if not x % 10 and not y % 10:
continue
for each_letter in str(x):
if each_letter in str(y) \
and x != y \
and int(str(y).replace(each_letter, '', 1)) != 0 \
and int(str(x).replace(each_letter, '', 1))/int(str(y).replace(each_letter, '', 1)) == x/y:
s_list.append((y, x))
s_list = list(set(s_list))
# 求 x,y (x<y) 的最大公约数
x = functools.reduce(lambda x1, x2: x1*x2, [each[1] for each in s_list])
y = functools.reduce(lambda x1, x2: x1 * x2, [each[0] for each in s_list])
tmp = y
while True:
if not y % tmp and not x % tmp:
result.append(x/tmp)
break
else:
tmp -= 1
return s_list, result
strange_list, result = get_strange_list()
print("分子分母：{}\n化简分母：{}\n用时：{}秒".format(strange_list, result, time.process_time()))

复制代码

永恒的蓝色梦想 · 发表于 2020-4-29 19:26:27

C++ 0ms

#include<iostream>
using namespace std;
int gcd(int a, int b) {
int c;
while (b) {
c = a % b;
a = b;
b = c;
}
return a;
}
bool judge(int a, int b) {
int c = a / 10, d = b % 10, e, f;
return a % 10 == b / 10 && a / (e = gcd(a, b)) == c / (f = gcd(c, d)) && b / e == d / f;
}
int main() {
int nume = 1, deno = 1, i, j;
for (i = 10; i < 100; i++) {
for (j = i + 1; j < 100; j++) {
if (judge(i, j)) {
nume *= i;
deno *= j;
}
}
}
cout << deno / gcd(nume, deno) << endl;
return 0;
}

复制代码

debuggerzh · 发表于 2020-8-13 17:27:44

100

Process returned 0 (0x0) execution time : 0.029 s
Press any key to continue.
暴力枚举，同时推得一些性质

#include<iostream>
#include<cmath>
using namespace std;
bool judge(int a,int b,int c,int d){
return a * b == c * d;
}
int gcd(int x,int y){
int r;
while(y){
r = x % y;
x = y;
y = r;
}
return x;
}
int main(){
int numertr = 1,divisr = 1;//初始化分子分母
for (int a1 = 1;a1 < 10;a1++){
for (int a2 = a1+1;a2 < 10;a2++){
int a = a1 * 10 + a2;
int b;
for (int a3 = a1+1;a3 < 10;a3++){
b = a3 * 10 + a1;
if (judge(a,a3,b,a2)) { numertr *= a2; divisr *= a3; }
}
for (int a4 = 1;a4 < 10;a4++){
b = a2 * 10 + a4;
if (judge(a,a4,b,a1)) { numertr *= a1; divisr *= a4; }
}
}
}
divisr /= gcd(numertr,divisr);
cout << divisr << endl;
return 0;
}

复制代码

有马_冬巳 · 发表于 2020-10-23 09:53:52

start = time.time()
for a in range(10,50):
if a % 10 != 0:
for b in range(10,100):
if b % 10 != 0 and a != b :
check = 0
sa = list(str(a))
sb = list(str(b))
for each in sa:
if each in sb:
same = each
check += 1
if check == 1:
sa.remove(same)
sb.remove(same)
if a / b == int(sa[0]) / int(sb[0]):
print("%d / %d" %(a,b))
end = time.time()
print("共用时%f秒" %(end - start))

复制代码

16 / 64
19 / 95
26 / 65
49 / 98
共用时0.004488秒

有马_冬巳 · 发表于 2020-10-23 10:17:11

start = time.time()
numer = 1
dino = 1
for a in range(10,50):
if a % 10 != 0:
for b in range(10,100):
if b % 10 != 0 and a != b :
check = 0
sa = list(str(a))
sb = list(str(b))
for each in sa:
if each in sb:
same = each
check += 1
if check == 1:
sa.remove(same)
sb.remove(same)
if a / b == int(sa[0]) / int(sb[0]):
numer *= a
dino *= b
print("%d / %d" %(a,b))
print("约分后分母为: %d" %(int(dino/numer)))
end = time.time()
print("共用时%f秒" %(end - start))

复制代码

16 / 64
19 / 95
26 / 65
49 / 98
约分后分母为: 100
共用时0.003944秒

a1351468657 · 发表于 2021-3-14 22:39:10

#include <stdio.h>
int MaxDiv(int, int);
int MaxDiv(int m, int n)
{
if (m == 0 || n == 0)
{
printf("有数字为0\n");
return -1;
}
int max, min, temp;
max = m > n ? m : n;
min = m < n ? m : n;
while (max % min)
{
temp = max % min;
max = min;
min = temp;
}
return min;
}
main()
{
int i, j, a, b, c, d, num = 1, den = 1;
double x, y;
for (i = 11; i < 100; i++)
{
for (j = i + 1; j < 100; j++)
{
a = i % 10;
b = i / 10;
c = j % 10;
d = j / 10;
if (a == 0 || b == 0 || c == 0 || d == 0)
{
continue;
}
if (a == c)
{
x = (double)b / d;
y = (double)i / j;
if (x == y)
{
num *= i;
den *= j;
printf("%d / %d\n", i, j);
}
}
if (a == d)
{
x = (double)b / c;
y = (double)i / j;
if (x == y)
{
num *= i;
den *= j;
printf("%d / %d\n", i, j);
}
}
if (b == c)
{
x = (double)a / d;
y = (double)i / j;
if (x == y)
{
num *= i;
den *= j;
printf("%d / %d\n", i, j);
}
}
if (b == d)
{
x = (double)a / c;
y = (double)i / j;
if (x == y)
{
num *= i;
den *= j;
printf("%d / %d\n", i, j);
}
}
}
}
i = MaxDiv(num, den);
printf("%d\n", den / i);
}

复制代码

答案为：
16 / 64
19 / 95
26 / 65
49 / 98

100

ft215378 · 发表于 2021-10-18 20:24:16

#找出具有一种奇怪约分性质的所有分数
from time import *
def deal_string(x, y):
if str(x)[0] == str(y)[0]:
      return int(str(x)[1]) / int(str(y)[1])
elif str(x)[0] == str(y)[1]:
      return int(str(x)[1]) / int(str(y)[0])
elif str(x)[1] == str(y)[0]:
      return int(str(x)[0]) / int(str(y)[1])
elif str(x)[1] == str(y)[1]:
      return int(str(x)[0]) / int(str(y)[0])

def get_strange_num():
strange_num = []
for a in range(10, 100):
      for b in range(10, 100):
         if a % 10 != 0 and b % 10 != 0:
            if a < b and (a / b) == deal_string(a, b):
                  strange_num.append('%s/%s' % (a, b))
return strange_num
start = time()
result = get_strange_num()

#计算
fenzi = 1
fenmu = 1
for each in result:
fenzi *= int(each[0] + each[1])
fenmu *= int(each[3] + each[4])
end = time()
print(fenmu//fenzi)
print("用时：%.9f秒" % (end - start))

guosl · 发表于 2022-1-3 15:17:56

/*
答案：100
耗时：0.0000015秒
*/
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int x, int y)
{
if (y == 0)
return x;
int z = x % y;
while (z != 0)
{
x = y;
y = z;
z = x % y;
}
return y;
}
int main(void)
{
int n = 1, d = 1;//分别保存特殊分数之积的分子和分母
//这样的特殊分数只牵涉到三个数，我们分别枚举它们
for (int a = 1; a <= 9; ++a)
{
for (int b = 0; b <= 9; ++b)
{
for (int c = 1; c <= 9; ++c)
{
int x = 10 * a + b;//构造分子
int y = 10 * b + c;//构造分母
if (x == 0 || y == 0)
continue;
if (x < y)//检查第一个要求
{
if (x * c == y * a)//检查第二个要求
{
//保存结果
n *= a;
d *= c;
}
}
else
{
swap(x, y);//相同的数字位置调换一下
if (x < y)//检查第一个要求
{
if (a * x == c * y)//检查第二个要求
{
//保存结果
n *= c;
d *= a;
}
}
}
}
}
}
int p = gcd(n, d);
d /= p;//约简分数
cout << d << endl;//输出分母
return 0;
}

复制代码

TLM · 发表于 2023-2-15 14:38:09

这个应该会快一些，但是计算量实在是太小了。重复10000测时间
100
Time:0.17248201370239258s

"""
(10i+j)/(10j+k)=i/k ==> (9i+j)k=10ij
(10i+j)/(10k+i)=j/k ==> (9k+i)j=10ik
(9i+j)k=10ij ==> k=10ij/(9i+j)
"""
import time
st=time.time()
def get():
# a=[]
b=1
c=1
for i in range(1,10):
for j in range(10):
if j==i:
continue
if not 10*i*j%(9*i+j)==0:
continue
k=10*i*j//(9*i+j)
if i==k or j==k:
continue
# a.append((min(i,k),j,max(i,k)))
b,c=b*min(i,k),c*max(i,k)
bb,cc=b,c
while bb>0 and cc>0:
if bb<cc:
cc=cc%bb
else:
bb=bb%cc
return c//max(bb,cc)
for i in range(10000):
get()
print(get())
print('Time:{}s'.format(time.time()-st))

复制代码

mathtimes · 发表于 2023-10-12 15:35:30

$ time ./main-v2
100

real 0m0.001s
user 0m0.000s
sys 0m0.001s

fn gcd(x:usize,y:usize) -> usize {
let (mut b, mut l) = (x, y);
if b < l {
(b,l) = (l,b)
}
while l != 0 {
b %= l;
(b,l) = (l,b)
}
b
}
fn bits(x: usize) -> usize {
let mut x = x;
let mut ans = 0;
while x != 0 && x % 10 != 0 {
ans ^= 1 << (x % 10 - 1);
x /= 10;
}
ans
}
fn main() {
let mut v = vec![];
for i in 10..99 {
for j in (i + 1)..=99 {
let t = bits(i)&bits(j);
if t.count_ones() != 1 {continue;}
let ri = (bits(i)^t).trailing_zeros() as usize + 1;
let rj = (bits(j)^t).trailing_zeros() as usize + 1;
if ri * j == rj * i {
v.push((ri, rj));
}
}
}
let i = v.iter().map(|x| x.0).product::<usize>();
let j = v.iter().map(|x| x.1).product::<usize>();
println!("{}", j / gcd(i, j));
}

复制代码

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

题目33：找出具有一种奇怪约分性质的所有分数

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

点评

评分

浏览过的版块