题目33：找出具有一种奇怪约分性质的所有分数
本帖最后由 欧拉计划 于 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: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;
} 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!=str_1 and str_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 # 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 此代码使用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)]) 迷雾少年 发表于 2016-8-29 17:03
16/64
26/65
49/98
去除普通个例 本帖最后由 永恒的蓝色梦想 于 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)
B = int(a)
C = int(b)
D = int(b)
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-------')
['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 == each:
list2.append(each + each)
elif each == each:
list2.append(each)
elif each == each:
list2.append(each + each)
else:
list2.append(each + each)
value_list1 = []
value_list2 = []
for each1 in list1:
value_list1.append(round(int(each1[:2]) / int(each1), 3))
for each2 in list2:
value_list2.append(round(int(each2) / int(each2[-1]), 3))
list3 = []
for i in range(len(list1)):
if value_list1 == value_list2:
list3.append(list1)
print(list3)
sum = 0
for each3 in list3:
sum += int(each3)
print(sum)
if __name__ == '__main__':
start = time()
EP033()
print('cost %.6f sec' % (time() - start)
分子分母：[(49, 98), (19, 95), (16, 64), (26, 65)]
化简分母：
用时：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, for each in s_list])
y = functools.reduce(lambda x1, x2: x1 * x2, 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())) 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;
} 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;
}
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) / int(sb):
print("%d / %d" %(a,b))
end = time.time()
print("共用时%f秒" %(end - start))
16 / 64
19 / 95
26 / 65
49 / 98
共用时0.004488秒
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) / int(sb):
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秒 #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 #找出具有一种奇怪约分性质的所有分数
from time import *
def deal_string(x, y):
if str(x) == str(y):
return int(str(x)) / int(str(y))
elif str(x) == str(y):
return int(str(x)) / int(str(y))
elif str(x) == str(y):
return int(str(x)) / int(str(y))
elif str(x) == str(y):
return int(str(x)) / int(str(y))
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 + each)
fenmu *= int(each + each)
end = time()
print(fenmu//fenzi)
print("用时：%.9f秒" % (end - start))
/*
答案：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;
}
这个应该会快一些，但是计算量实在是太小了。重复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)) $ 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));
}
页:
[1]