Prolog 人工智能语言中文论坛---打造优质Prolog学习交流园地

一个供Prolog爱好者学习与交流的地方


您没有登录。 请登录注册

[问题求解]求无限循环小数的循环节

浏览上一个主题 浏览下一个主题 向下  留言 [第1页/共1页]

1 [问题求解]求无限循环小数的循环节 于 周三 三月 28, 2012 3:15 am

编写一个谓词cycle/3,前两个参数为两个正整数A和B,第三个参数为自由变量。
调用该谓词后,第三个谓词合一为一个0-9的整数列表。
当A/B为结果为整数或有限小数时,列表中只有一个元素0,
当A/B为无限循环小数时,列表中为这个小数的循环节。

调用示例:
?- cycle(3,4,C) .
C = [0] % 因为 3/4 = 0.250000...
?- cycle(4,3,C) .
C = [3] % 因为 4/3 = 1.333...
?- cycle(1,7,C) .
C = [1,4,2,8,5,7] % 因为 1/7 = 0.142857142857...
对于最后一个例子,C=[1,4,2,8,5,7]或C=[4,2,8,5,7,1]都是正确结果,这里只要求程序输出一个结果即可。

查阅用户资料
wdx04 写道::编写一个谓词cycle/3,前两个参数为两个正整数A和B,第三个参数为自由变量。
调用该谓词后,第三个谓词合一为一个0-9的整数列表。
当A/B为结果为整数或有限小数时,列表中只有一个元素0,
当A/B为无限循环小数时,列表中为这个小数的循环节。

调用示例:
?- cycle(3,4,C) .
C = [0] % 因为 3/4 = 0.250000...
?- cycle(4,3,C) .
C = [3] % 因为 4/3 = 1.333...
?- cycle(1,7,C) .
C = [1,4,2,8,5,7] % 因为 1/7 = 0.142857142857...
对于最后一个例子,C=[1,4,2,8,5,7]或C=[4,2,8,5,7,1]都是正确结果,这里只要求程序输出一个结果即可。

哈哈,w大的这个题目是出来让大家动动脑还是自己遇到的难题?
感觉上最后一个例子,应该要是142857比较合理,因为小数第一位是从1开始。

查阅用户资料 http://prolog.longluntan.net
wdx04 写道::编写一个谓词cycle/3,前两个参数为两个正整数A和B,第三个参数为自由变量。
调用该谓词后,第三个谓词合一为一个0-9的整数列表。
当A/B为结果为整数或有限小数时,列表中只有一个元素0,
当A/B为无限循环小数时,列表中为这个小数的循环节。

调用示例:
?- cycle(3,4,C) .
C = [0] % 因为 3/4 = 0.250000...
?- cycle(4,3,C) .
C = [3] % 因为 4/3 = 1.333...
?- cycle(1,7,C) .
C = [1,4,2,8,5,7] % 因为 1/7 = 0.142857142857...
对于最后一个例子,C=[1,4,2,8,5,7]或C=[4,2,8,5,7,1]都是正确结果,这里只要求程序输出一个结果即可。


试了一下,感觉这样应该可以了。
写的过程中有遇到过一个麻烦的问题就是prolog算小数有时不太精确啊,
所以最后我改用String来处理:

代码:
cycle(N1,N2,Cycle) :-
  X is N1/N2, fractional_to_list(X,L), append(A,B,L), append(C,D,B),
  is_cycle(C,Cycle_Ascii), string_to_list(Cycle, Cycle_Ascii),!.

cycle(N1,N2,Cycle) :- string_to_list(Cycle, [48]).


fractional_to_list(Float,List) :- string_to_list(Float, L), append(A,List,L), last(A,46).

is_cycle(List, A) :-
  append(A,B,List), length(A,N1), length(List,N2), N1>0, N2>0, Y is N2/N1, integer(Y), Y \= 1,
  uniform_list(A,Y,List2), append(List2, List3), List3 = List.

uniform_list(Form, Num, List) :- list_to_set(List, Set), length(Set,1), nth1(1,Set,Form), length(List,Num),!.

查阅用户资料 http://prolog.longluntan.net
网上看到的一个题,不是自己想的,大家一起做做。
有两个问题,一是输出格式应该是一个数字列表而不是字符串,二是对某些输入得不出正确结果。
例如cycle(1,17,L),你返回L="8",应为[0,5,8,8,2,3,5,2,9,4,1,1,7,6,4,7],后面1/19,1/23等等都是类似的情况。

查阅用户资料
wdx04 写道::网上看到的一个题,不是自己想的,大家一起做做。
有两个问题,一是输出格式应该是一个数字列表而不是字符串,二是对某些输入得不出正确结果。
例如cycle(1,17,L),你返回L="8",应为[0,5,8,8,2,3,5,2,9,4,1,1,7,6,4,7],后面1/19,1/23等等都是类似的情况。

我用的SWI-Prolog,以1/17为例,
Prolog算出后只显示18位小数,而这个循环节有16个数字,
就无法判断出循环的部分,比18位再小的位数Prolog又算不精确,
我暂时也没想到什么法子解决。

可能得自己先写一个除法程序,每一次除能得到下一位小数,
比如1/7,不是直接让X is 1/7,因为这样只能显示十几位小数,
而改用X为1,Y为7,X<Y,所以X先乘以10,变成10/7,就能先得到第一位小数1,
然后就是重复这个原理,10/7后的余数是3,3<7,所以3乘以10变成30再除以7,
得出第2位小数4,余数是2,然后……一直下去。

在这个自己写的除法运算基础上,每除出一位小数,
就检查一遍是否已出现循环。
我觉得这样应该能解决这个问题,
有空我再试看看。

查阅用户资料 http://prolog.longluntan.net

6 回复: [问题求解]求无限循环小数的循环节 于 周三 三月 28, 2012 11:26 am

我的代码,基本上就是你那个思路,写的比较乱。
代码:

:- ensure_loaded(library(lists)).

% 计算最大公约数
gcd1(X, Y, Gcd) :- X1 is X mod Y, (X1 == 0 -> Gcd = Y; gcd(X1, Y, Gcd)).
gcd(X, Y, Gcd) :- (X >= Y -> gcd1(X, Y, Gcd) ; gcd1(Y, X, Gcd)).

% 递归谓词2,寻找非负整数k,使X*(10^k) MOD Y == M,并计算C=X*(10^k)//Y
cycle2(X, Y, M, C) :- gcd(X, Y, Gcd),
(Gcd > 1 -> X1 is X // Gcd, Y1 is Y // Gcd, M1 is X1 mod Y1, (M1 == 0 -> C is 0; cycle1(M1, Y1, C))
;
M2 is X mod Y, (M2 == 0 -> C is 0; (M == M2 -> !, C is X // Y; X2 is X * 10, cycle2(X2, Y, M, C)))
).

% 递归谓词1
cycle1(X, Y, C) :- gcd(X, Y, Gcd),
(Gcd > 1 -> X1 is X // Gcd, Y1 is Y // Gcd, cycle1(X1, Y1, C)
;
M is X mod Y, X1 is X * 10, cycle2(X1, Y, M, C)
).

% 整数转换为列表,列表长度为第二个参数的十进制位数-1
int_to_list(_, 1, []) :- !.
int_to_list(C, N, [H|L]) :- H is C mod 10, C1 is C // 10, N1 is N // 10, int_to_list(C1, N1, L).

% 主谓词
cycle(X, Y, L) :- cycle1(X, Y, C), N is (Y * C + X) // X, int_to_list(C, N, L1), (length(L1, 0) -> L = [0] ; reverse(L1, L)).

查阅用户资料

7 回复: [问题求解]求无限循环小数的循环节 于 周三 三月 28, 2012 11:36 am

wdx04 写道::网上看到的一个题,不是自己想的,大家一起做做。
有两个问题,一是输出格式应该是一个数字列表而不是字符串,二是对某些输入得不出正确结果。
例如cycle(1,17,L),你返回L="8",应为[0,5,8,8,2,3,5,2,9,4,1,1,7,6,4,7],后面1/19,1/23等等都是类似的情况。


这个可以了:

代码:
:- dynamic solution/2.

cycle(N1,N2,Cycle) :- repeat, not(retract(solution(X,Y))), loop(N1,N2,[]), solution(Cycle,_).

loop(N1,N2,OriList) :-
  next_number(N1,N2,Num,Remain), append(OriList, [Num], NewList),
  check_cycle(NewList),
  (solution(S,X), X = 5 -> true ; loop(Remain,N2,NewList)).

next_number(N1,N2,Num,Remain) :-
  N3 is N1 * 10, (N3 =< N2 -> Num =0, Remain = N3 ; Num is floor(N3/N2), Remain is N3 - Num * N2).

check_cycle(List) :-
  append(D,C,List), is_cycle(C,Cycle),
  (solution(Cycle,X) ->
  X1 is X + 1, retract(solution(Cycle,X)), asserta(solution(Cycle,X1)) ;
  asserta(solution(Cycle,1))).
check_cycle(_).

is_cycle(List, A) :-
  append(A,B,List), length(A,N1), length(List,N2), N1>0, N2>0, Y is N2/N1, integer(Y), Y \= 1,
  uniform_list(A,Y,List2), append(List2, List3), List3 = List.

uniform_list(Form, Num, List) :- list_to_set(List, Set), length(Set,1), nth1(1,Set,Form), length(List,Num),!.

查阅用户资料 http://prolog.longluntan.net

8 回复: [问题求解]求无限循环小数的循环节 于 周三 三月 28, 2012 11:45 am

wdx04 写道::我的代码,基本上就是你那个思路,写的比较乱。
代码:

:- ensure_loaded(library(lists)).

% 计算最大公约数
gcd1(X, Y, Gcd) :- X1 is X mod Y, (X1 == 0 -> Gcd = Y; gcd(X1, Y, Gcd)).
gcd(X, Y, Gcd) :- (X >= Y -> gcd1(X, Y, Gcd) ; gcd1(Y, X, Gcd)).

% 递归谓词2,寻找非负整数k,使X*(10^k) MOD Y == M,并计算C=X*(10^k)//Y
cycle2(X, Y, M, C) :- gcd(X, Y, Gcd),
(Gcd > 1 -> X1 is X // Gcd, Y1 is Y // Gcd, M1 is X1 mod Y1, (M1 == 0 -> C is 0; cycle1(M1, Y1, C))
;
M2 is X mod Y, (M2 == 0 -> C is 0; (M == M2 -> !, C is X // Y; X2 is X * 10, cycle2(X2, Y, M, C)))
).

% 递归谓词1
cycle1(X, Y, C) :- gcd(X, Y, Gcd),
(Gcd > 1 -> X1 is X // Gcd, Y1 is Y // Gcd, cycle1(X1, Y1, C)
;
M is X mod Y, X1 is X * 10, cycle2(X1, Y, M, C)
).

% 整数转换为列表,列表长度为第二个参数的十进制位数-1
int_to_list(_, 1, []) :- !.
int_to_list(C, N, [H|L]) :- H is C mod 10, C1 is C // 10, N1 is N // 10, int_to_list(C1, N1, L).

% 主谓词
cycle(X, Y, L) :- cycle1(X, Y, C), N is (Y * C + X) // X, int_to_list(C, N, L1), (length(L1, 0) -> L = [0] ; reverse(L1, L)).

哈哈,我们两个都写出来了,
现在两个不一样的代码但都可以做到这件事。

查阅用户资料 http://prolog.longluntan.net

9 回复: [问题求解]求无限循环小数的循环节 于 周四 三月 29, 2012 12:23 pm

Mercury Liao 写道::
哈哈,我们两个都写出来了,
现在两个不一样的代码但都可以做到这件事。
嗯,你的也是对的

查阅用户资料

浏览上一个主题 浏览下一个主题 返回页首  留言 [第1页/共1页]

您在这个论坛的权限:
不能在这个论坛回复主题