三角形の形状の分析

 投稿者：山中和義  投稿日：2012年 1月15日(日)10時22分55秒
  !（三角形の形状の分析）
!自然数M,Nは、M≧Nとする。
!点(x,y)は、領域0≦x≦M、0≦y≦N内の格子点とする。
!(M+1)(N+1)個の格子点から3つを選んでできる点(x,y)の組を頂点とする三角形を分類せよ。


!参考サイト


LET M=3 !0≦x≦M
LET N=M !0≦y≦N


LET K=0 !三角形が不成立
LET P=0 !直角をはさむ２辺が軸に平行な直角三角形
LET Q=0 !直角二等辺三角形
LET R=0 !直角三角形
LET S=0 !二等辺三角形
LET T=0 !鈍角三角形

DIM X(0 TO 3-1),Y(0 TO 3-1) !三角形の頂点の座標

LET Z=(N+1)*(M+1) !格子点の個数

PRINT "頂点番号"
FOR i=N TO 0 STEP -1
   FOR j=0 TO M
      PRINT USING "###": (M+1)*i+j;
   NEXT j
   PRINT
NEXT i
PRINT


FOR A=0 TO Z-3 !組合せ C((M+1)(N+1),3)
   LET X(0)=MOD(A,M+1) !座標へ
   LET Y(0)=INT(A/(M+1))
   FOR B=A+1 TO Z-2
      LET X(1)=MOD(B,M+1)
      LET Y(1)=INT(B/(M+1))
      FOR C=B+1 TO Z-1
         LET X(2)=MOD(C,M+1)
         LET Y(2)=INT(C/(M+1))
         !!PRINT A;B;C; "(";X(0);Y(0);") ("; X(1);Y(1);") ("; X(2);Y(2);")" !debug
         PRINT "("; STR$(A);","; STR$(B);","; STR$(C);")= ";


         LET U1=X(0)-X(3-1) !辺c　※辺を反時計まわりに巡回するベクトルを考える
         LET V1=Y(0)-Y(3-1)

         FOR i=0 TO 3-1 !３つの外角と辺に対して

            LET U2=X(MOD(i+1,3))-X(i) !辺b
            LET V2=Y(MOD(i+1,3))-Y(i)


            LET G=U1*V2-U2*V1 !外積 BCsin(∠A) ≠0, ＝0, 符号
            IF G<>0 THEN !三角形が成立するなら
               LET FLG=0

               IF G<0 AND i=0 THEN PRINT "時計まわり　";

               IF U1*U1+V1*V1=U2*U2+V2*V2 THEN !二等辺三角形
                  LET S=S+1
                  PRINT CHR$(ORD("a")+MOD(i+1,3));"=";CHR$(ORD("a")+MOD(i+2,3));"　"; !b=c
                  LET FLG=1
               END IF


               LET F=U1*U2+V1*V2 !内積 BCcos(∠A) ＝0, ＜0, ＞0
               IF F=0 THEN !外角は直角なので、内角も直角
                  LET R=R+1
                  PRINT "∠";CHR$(ORD("A")+i);"=直角";

                  IF FLG=1 THEN LET Q=Q+1 !直角二等辺三角形

                  IF U1*0-1*V1=0 OR U1*1-0*V1=0 THEN !X軸(1,0), Y軸(0,1)との外積
                     LET P=P+1
                     PRINT "　軸に平行";
                  END IF
                  EXIT FOR

               ELSEIF F>0 THEN !外角は鋭角なので、内角は鈍角
                  LET T=T+1
                  PRINT "∠";CHR$(ORD("A")+i);"=鈍角";
                  EXIT FOR

               ELSE
               !次へ

               END IF

            ELSE !不成立
               LET K=K+1
               PRINT "△ABCは不成立";
               EXIT FOR

            END IF


            LET U1=U2 !次へ
            LET V1=V2
         NEXT i
         PRINT

      NEXT C
   NEXT B
NEXT A


LET W=COMB((M+1)*(N+1),3)
PRINT "格子点の選び方は、"; W; "通り"

PRINT "三角形="; P; R; Q; S; T; W-K; K;"個"
PRINT "鋭角三角形="; (W-K)-(R+T)


PRINT m*(m+1)*n*(n+1);"個" !m*(m+1)*n*(n+1)、m=nなら、{n(n+1)}^2


END

 		 

Re: 三角形の形状の分析

 投稿者：山中和義  投稿日：2012年 1月16日(月)10時21分1秒
  > No.1725[元記事へ]

> （三角形の形状の分析）
> 自然数M,Nは、M≧Nとする。
> 点(x,y)は、領域0≦x≦M、0≦y≦N内の格子点とする。
> (M+1)(N+1)個の格子点から3つを選んでできる点(x,y)の組を頂点とする三角形を分類せよ。

鈍角三角形と鋭角三角形の発生比率は？

モンテカルロ法による

LET M=10^8
LET N=M
LET S=0 !発生数
LET T=10^6 !試行回数
FOR i=1 TO T
   LET X0=INT(RND*M) !0≦x＜M　1点目
   LET Y0=INT(RND*N) !0≦y＜N
   DO
      LET X1=INT(RND*M) !0≦x＜M
      LET Y1=INT(RND*N) !0≦y＜N
   LOOP UNTIL NOT( X1=X0 AND Y1=Y0 ) !2点目
   DO
      LET X2=INT(RND*M) !0≦x＜M
      LET Y2=INT(RND*N) !0≦y＜N
   LOOP UNTIL NOT( (X2=X0 AND Y2=Y0) OR (X2=X1 AND Y2=Y1) ) !3点目
   !PRINT X0;Y0; X1;Y1; X2;Y2 !debug

   LET AA=(X2-X1)^2+(Y2-Y1)^2 !辺の長さの２乗
   LET BB=(X0-X2)^2+(Y0-Y2)^2
   LET CC=(X1-X0)^2+(Y1-Y0)^2
   IF BB+CC<AA OR CC+AA<BB OR AA+BB<CC THEN !余弦定理BCcosA=B^2+C^2-A^2より、負なら∠Aは鈍角
      LET S=S+1
   END IF
NEXT i
PRINT S;T; S/T; (T-S)/T
PRINT S/(T-S); ":"; 1
END


実行結果
725656  1000000  .725656  .274344
2.64505875834718 : 1

 		 

Re: 三角形の形状の分析

 投稿者：山中和義  投稿日：2012年 1月19日(木)21時25分52秒
  > No.1726[元記事へ]



!（直線の分析）
!自然数M,Nは、M≧Nとする。
!点(x,y)は、領域0≦x≦M、0≦y≦N内の格子点とする。
!(M+1)(N+1)個の格子点の中から2つ以上の点を通る直線は何本あるか。

!参考サイト


LET M=3 !0≦x≦M
LET N=M !0≦y≦N

LET K=0 !他の線分と重なる本数

LET Z=(N+1)*(M+1) !格子点の個数

PRINT "頂点番号"
FOR i=N TO 0 STEP -1
   FOR j=0 TO M
      PRINT USING "###": (M+1)*i+j;
   NEXT j
   PRINT
NEXT i
PRINT


DIM S(MAX(M,N)-1) !通過する格子点の数iの直線の本数S(i)
MAT S=ZER

FOR A=0 TO Z-2 !組合せ C((M+1)(N+1),2)
   LET XA=MOD(A,M+1) !座標へ
   LET YA=INT(A/(M+1))
   FOR B=A+1 TO Z-1
      LET XB=MOD(B,M+1)
      LET YB=INT(B/(M+1))

      PRINT "("; STR$(A); ","; STR$(B); ")";


      LET DX=XB-XA !線分ABのベクトルを考える
      LET DY=YB-YA


      LET G=gcd(ABS(DX),ABS(DY)) !正規化する
      LET DXX=DX/G
      LET DYY=DY/G

      LET XX=XA-DXX !線分ABの点Aを延ばす
      LET YY=YA-DYY
      IF (XX<0 OR XX>M) OR (YY<0 OR YY>N) THEN !領域外なら
         LET XX=XB+DXX !線分ABの点Bを延ばす
         LET YY=YB+DYY
         IF (XX<0 OR XX>M) OR (YY<0 OR YY>N) THEN !領域外なら
            LET FLG=0
         ELSE
            LET FLG=1 !点B'あり
         END IF
      ELSE
         LET FLG=1 !点A'あり
      END IF
      IF FLG=1 THEN !線分A'B, AB'に重なる
         LET K=K+1
         PRINT "　×";
      END IF


      LET W=G-1 !通過する格子点の数
      IF W>0 THEN
         PRINT W;
         IF FLG=0 THEN LET S(W)=S(W)+1
      END IF
      PRINT


   NEXT B
NEXT A

LET W=COMB((M+1)*(N+1),2)
PRINT "格子点の選び方は、"; W; "通り"

PRINT "重なるのは、"; K; "通り"
PRINT "よって、"; W-K; "通り"

MAT PRINT S;




!（三角形の形状の分析）
!自然数M,Nは、M≧Nとする。
!点(x,y)は、領域0≦x≦M、0≦y≦N内の格子点とする。
!(M+1)(N+1)個の格子点から3つを選んでできる点(x,y)の組を頂点とする三角形を分類せよ。
!
!(1)三角形
!(2)三角形が不成立

!参考サイト

!三角形が不成立は、3点が一直線上に並ぶときである。
!したがって、上記の結果を利用して得られる。

LET W=0
FOR i=1 TO MAX(M,N)-1
   LET W=W+S(i)*COMB(i+2,3)
NEXT i
PRINT COMB((M+1)*(N+1),3)-W; "通り"


END


EXTERNAL FUNCTION gcd(a,b) !最大公約数
DO UNTIL b=0
   LET t=b
   LET b=MOD(a,b)
   LET a=t
LOOP
LET gcd=a
END FUNCTION


実行結果

頂点番号
12 13 14 15
  8  9 10 11
  4  5  6  7
  0  1  2  3

(0,1)　×
(0,2)　× 1
(0,3) 2
(0,4)　×
(0,5)　×
(0,6)
(0,7)
(0,8)　× 1
(0,9)
(0,10)　× 1
(0,11)
(0,12) 2
(0,13)
(0,14)
(0,15) 2
(1,2)　×
(1,3)　× 1
(1,4)
(1,5)　×
(1,6)　×
(1,7)
(1,8)
(1,9)　× 1
(1,10)
(1,11) 1
(1,12)
(1,13) 2
(1,14)
(1,15)
(2,3)　×
(2,4)
(2,5)　×
(2,6)　×
(2,7)
(2,8) 1
(2,9)
(2,10)　× 1
(2,11)
(2,12)
(2,13)
(2,14) 2
(2,15)
(3,4)
(3,5)
(3,6)　×
(3,7)　×
(3,8)
(3,9)　× 1
(3,10)
(3,11)　× 1
(3,12) 2
(3,13)
(3,14)
(3,15) 2
(4,5)　×
(4,6)　× 1
(4,7) 2
(4,8)　×
(4,9)　×
(4,10)
(4,11)
(4,12)　× 1
(4,13)
(4,14) 1
(4,15)
(5,6)　×
(5,7)　× 1
(5,8)　×
(5,9)　×
(5,10)　×
(5,11)
(5,12)
(5,13)　× 1
(5,14)
(5,15)　× 1
(6,7)　×
(6,8)
(6,9)　×
(6,10)　×
(6,11)　×
(6,12)　× 1
(6,13)
(6,14)　× 1
(6,15)
(7,8)
(7,9)
(7,10)　×
(7,11)　×
(7,12)
(7,13) 1
(7,14)
(7,15)　× 1
(8,9)　×
(8,10)　× 1
(8,11) 2
(8,12)　×
(8,13)
(8,14)
(8,15)
(9,10)　×
(9,11)　× 1
(9,12)　×
(9,13)　×
(9,14)　×
(9,15)
(10,11)　×
(10,12)
(10,13)　×
(10,14)　×
(10,15)　×
(11,12)
(11,13)
(11,14)
(11,15)　×
(12,13)　×
(12,14)　× 1
(12,15) 2
(13,14)　×
(13,15)　× 1
(14,15)　×
格子点の選び方は、 120 通り
重なるのは、 58 通り
よって、 62 通り
4  10

516 通り

 		 

戻る