|
|
> No.1480[元記事へ]
永野護さんへのお返事です。
> 質問１
素数の中から、条件を満たすものを選びます。
!HIGGS素数
! Higgs' primes: a(n+1) = next prime such that a(n+1)-1 | (a(1)...a(n))^3.
! 2, 3, 5, 7, 11, 13, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 101, 107, 109, 127, 131, 139, 149, 151, 157, 167, 173, 179, 181, 191, 197, 199, 211, 223, 229, 233, 251, 263, 269, 271, 277, 281, 283, 293, 311, 313, 317, 331, 347, 349, 359
OPTION ARITHMETIC RATIONAL !多桁の整数
LET N=50
DIM P(N)
CALL HIGGSPrimeList(N,P) !ｎ個のHIGGS素数列
MAT PRINT P;
FOR i=1 TO 359
IF HIGGSPrimeQ(i)<>0 THEN PRINT i; !HIGGS素数列の判定
NEXT i
PRINT
END
!試行割算法
EXTERNAL FUNCTION PrimeQ(n) !素数判定 1:素数、0:素数でない
OPTION ARITHMETIC RATIONAL !多桁の整数
LET PrimeQ=0
IF n<2 OR n<>INT(n) THEN EXIT FUNCTION !引数を確認する
!２以上の自然数なら
IF MOD(n,2)=0 THEN !２の倍数
IF n=2 THEN LET PrimeQ=1 !２は素数
ELSEIF MOD(n,3)=0 THEN !３の倍数
IF n=3 THEN LET PrimeQ=1 !３は素数
ELSE
LET k=5
DO WHILE k*k<=n !√nまで検証する
IF MOD(n,k)=0 THEN !5,11,17,23,29,…
EXIT FUNCTION
ELSEIF MOD(n,k+2)=0 THEN !7,13,19,25,31,…
EXIT FUNCTION
END IF !+1,+3,+5は２の倍数（偶数）、+1,+4は３の倍数、+5は５の倍数
LET k=k+6
LOOP
LET PrimeQ=1 !最後まで割り切れなければ、素数である
END IF
END FUNCTION
!HIGGS素数
EXTERNAL FUNCTION HIGGSPrimeQ(n) !HIGGS素数判定 1:HIGGS素数、0:HIGGS素数でない
OPTION ARITHMETIC RATIONAL !多桁の整数
LET HIGGSPrimeQ=0
IF PrimeQ(n)=0 THEN EXIT FUNCTION !素数でなければ、HIGGS素数でない
IF n=2 THEN !２はHIGGS素数である
LET HIGGSPrimeQ=1
EXIT FUNCTION
END IF
LET t=2^3
LET k=3 !ｎ未満のHIGGS素数列を得る
DO WHILE k<n
IF PrimeQ(k)<>0 THEN
IF MOD(t,k-1)=0 THEN !P(k+1)-1|(P(1)P(2)…P(k))^3なら
LET t=t*k^3 !(P(1)P(2)…P(k))^3
END IF
END IF
LET k=k+2
LOOP
IF MOD(t,n-1)=0 THEN LET HIGGSPrimeQ=1 !P(n+1)-1|(P(1)P(2)…P(n))^3なら
END FUNCTION
EXTERNAL SUB HIGGSPrimeList(n,p()) !ｎ個のHIGGS素数列を返す
OPTION ARITHMETIC RATIONAL !多桁の整数
IF n<1 THEN EXIT SUB !引数を確認する
LET c=1 !見つけた個数
LET p(c)=2 !２はHIGGS素数
IF n=1 THEN EXIT SUB
LET t=2^3
LET c=2
LET p(c)=3
IF n=2 THEN EXIT SUB
LET t=t*3^3
LET k=5
DO
IF PrimeQ(k)<>0 THEN !5,11,17,23,29,… が素数なら
IF MOD(t,k-1)=0 THEN !P(n+1)-1|(P(1)P(2)…P(n))^3なら
LET c=c+1
LET p(c)=k
IF c=n THEN EXIT DO
LET t=t*k^3 !(P(1)P(2)…P(n))^3
END IF
END IF
IF PrimeQ(k+2)<>0 THEN !7,13,19,25,31,…
IF MOD(t,k+1)=0 THEN !P(n+1)-1|(P(1)P(2)…P(n))^3なら
LET c=c+1
LET p(c)=k+2
IF c=n THEN EXIT DO
LET t=t*(k+2)^3
END IF
END IF
LET k=k+6 !次へ
LOOP
END SUB
> 質問２
解き方は自己流ですが、、、
!問題
!節点Ａ～Ｅまでの最短距離を求めよ。枝の数字は距離とする。
! ７
! ┌→Ｄ
! ５│７↓２
! Ａ→Ｂ→Ｅ
! │２↑ ↑
! └→Ｃ─┘
! ４ ９
!答え
!枝x1(A,B)、x2(A,C)、x3(C,B)、x4(B,D)、x5(B,E)、x6(C,E)、x7(D,E)とする。
! x4
! ┌→Ｄ
! x1│x5↓x7
! Ａ→Ｂ→Ｅ
! │x3↑ ↑
! └→Ｃ─┘
! x2 x6
!
!制約条件の式の作り方
!左辺
! 節点xに対して、入っている枝は-1、出ている枝に1として、総和をとる。
!右辺
! 節点xが出発点なら１、到着点なら-1、それ以外は０とする。
!
! たとえば節点Aなら、入っている枝はなし。出ている枝はx1,x2。出発点なので
! x1+x2=1 となる。
!
!目的関数
! 5*x1 + 4*x2 + 2*x3 + 7*x4 + 7*x5 + 9*x6 + 2*x7 の最小値
!制約条件
! 節点A x1+x2=1
! 節点B -x1-x3+x4+x5=0
! 節点C -x2+x3+x6=0
! 節点D -x4+x7=0
! 節点E -x5-x6-x7=-1
! x1,x2,x3,x4,x5,x6,x7∈{0,1}
!
!これを解いて、枝xi=1なら最短経路に含まれる。
LET N=7 !変数の数
LET M=5 !制約条件の数
DIM A(M+1,N+1) !係数行列
DATA 1, 1, 0, 0, 0, 0, 0, 1
DATA -1, 0,-1, 1, 1, 0, 0, 0
DATA 0,-1, 1, 0, 0, 1, 0, 0
DATA 0, 0, 0,-1, 0, 0, 1, 0
DATA 0, 0, 0, 0,-1,-1,-1, -1
DATA 5, 4, 2, 7, 7, 9, 2, 0
MAT READ A
LET cMAX=9999
DIM x(N)
FOR i=1 TO 2^N-1 !全パターンを検証する
LET t=i
LET c=0
DO WHILE t>0 !２進法へ
LET c=c+1
LET x(c)=MOD(t,2)
LET t=INT(t/2)
LOOP
FOR j=1 TO M !制約条件を確認する
LET t=0
FOR k=1 TO N
LET t=t+A(j,k)*x(k)
NEXT k
IF t<>A(j,N+1) THEN EXIT FOR !１つでも満たさなければ終了
NEXT j
IF j>M THEN !制約条件を満たすなら
LET t=0 !目的関数を計算する
FOR k=1 TO N
LET t=t+A(M+1,k)*x(k)
NEXT k
IF t<=cMAX THEN !最小なら
LET cMAX=t
MAT PRINT x; !xiと値を表示する
PRINT t
END IF
END IF
NEXT i
END
|
|