Project Euler 63
の乗の対数(底10)をとることを考えます.
それによっての桁数が分かるので,
を満たせば良いと分かります.右辺より,
左辺より,
この左辺は,大で,10に近づき,9.0を超えると上の不等式を満たすは存在しなくなります.
を得ます.従って,について,3つ上の不等式を満たすの個数を足し合わせれば答えが求まります.
Project Euler 62
13, 23, 33, ... の立方数の各桁の数字をカウントしたとき,
0~9の個数が同じになる立方数は,互いに桁の置き換えを持つ立方数であることに気付きました.
0の個数ごとに枝分かれをし,そのそれぞれのノードから,1の個数ごとに枝分かれをし,...
という多分木を作ることで,ある立方数について各桁の数字のカウント値によってその木を手繰ることを考えると,
同じ葉に行き着く立方数は,最初の説明より,互いに桁の置き換えを持つ立方数だと分かります.
そして同じ葉に行き着く立方数が5つ現れたとき,最初にその葉に行き着いた立方数がこの問題の答えになります.
(50msで答えを求められるのですが,早すぎて自分でも驚いています)
Project Euler 61
4桁の各多角数ごとに上二桁が等しい数でリストを作り,
順序集合内に多角数が一種類ずつ現れるように,深さ優先探索をしました.
ベジエ曲線
以下のプログラムは2次ベジェ曲線を書きます.
PicturePanel.java
package beziercurve; import java.awt.Color; import java.awt.Graphics; import java.awt.Point; import java.util.ArrayList; import java.util.List; import javax.swing.JPanel; public class PicturePanel extends JPanel implements Runnable { Thread refresh = null; List<Ball> ball; List<Ball> p; Ball bezierBall; List<Point> locusPoint; double[] vx, vy; double d; // 線分の分割数 double t; // 時刻 public PicturePanel() { if( refresh == null ) { refresh = new Thread(this); refresh.start(); } t = 0; d = 200; p = new ArrayList<Ball>(); p.add(new Ball(new Point(100, 350), 10, 0, 0, Color.black)); p.add(new Ball(new Point(300, 80), 10, 0, 0, Color.black)); p.add(new Ball(new Point(500, 400), 10, 0, 0, Color.black)); vx = new double[p.size() - 1]; vy = new double[p.size() - 1]; for( int i = 0; i < p.size() - 1; i++ ) { vx[i] = (p.get(i + 1).getCenterPoint().x - p.get(i).getCenterPoint().x) / d; vy[i] = (p.get(i + 1).getCenterPoint().y - p.get(i).getCenterPoint().y) / d; } ball = new ArrayList<Ball>(); for( int i = 0; i < p.size() - 1; i++ ) { ball.add(new Ball(p.get(i).getCenterPoint(), 15, vx[i], vy[i], Color.CYAN)); } bezierBall = new Ball(p.get(0).getCenterPoint(), 2, vx[0], vy[0], Color.BLACK); locusPoint = new ArrayList<Point>(); } @Override public void paintComponent(Graphics g) { double vx, vy; super.paintComponent(g); // 線分の描画 for( int i = 0; i < p.size() - 1; i++ ) { g.setColor(Color.BLACK); g.drawLine(p.get(i).getCenterPoint().x, p.get(i).getCenterPoint().y, p.get(i + 1).getCenterPoint().x, p.get(i + 1).getCenterPoint().y); } for( int i = 0; i < p.size() - 2; i++ ) { g.setColor(Color.red); g.drawLine(ball.get(i).getCenterPoint().x, ball.get(i).getCenterPoint().y, ball.get(i + 1).getCenterPoint().x, ball.get(i + 1).getCenterPoint().y); } // 始点・終点の描画 for( Ball elemBall : p ) { g.setColor(elemBall.getColor()); g.fillOval(elemBall.getRectangle().x, elemBall.getRectangle().y, elemBall.getRectangle().width, elemBall.getRectangle().height); } // 線分上を動く円の描画 for( int i = 0; i < p.size() - 1; i++ ) { g.setColor(ball.get(i).getColor()); g.fillOval(ball.get(i).getPoint().x, ball.get(i).getPoint().y, ball.get(i).getRectangle().width, ball.get(i).getRectangle().height); ball.get(i).Move(p.get(i), t); } vx = (ball.get(1).getCenterPoint().x - ball.get(0).getCenterPoint().x) / d; vy = (ball.get(1).getCenterPoint().y - ball.get(0).getCenterPoint().y) / d; bezierBall.setV(vx, vy); bezierBall.Move(ball.get(0), t); g.setColor(bezierBall.getColor()); g.fillOval(bezierBall.getPoint().x, bezierBall.getPoint().y, bezierBall.getRectangle().width, bezierBall.getRectangle().height); g.setColor(bezierBall.getColor()); for( Point p : locusPoint ) { g.fillOval(p.x, p.y, bezierBall.getRectangle().width, bezierBall.getRectangle().height); } if( t > d ) { t = 0; locusPoint.clear(); } else { t += 1.0; locusPoint.add(bezierBall.getPoint()); } } @Override public void run() { while( true ) { repaint(); try { if( t > d ) { Thread.sleep(300); } else { Thread.sleep(10); } } catch (Exception e) { } } } }
Ball.java
package beziercurve; import java.awt.Color; import java.awt.Point; import java.awt.Rectangle; public class Ball { private Point point; private int r; private Rectangle rectangle; private double vx, vy; private Color color; public Ball(Point point, int r, double vx, double vy, Color color) { this.point = new Point(point.x - r, point.y - r); this.r = r; this.rectangle = new Rectangle(this.point.x, this.point.y, 2 * r, 2 * r); this.vx = vx; this.vy = vy; this.color = color; } public Point getPoint() { return new Point(point); } public Point getCenterPoint() { return new Point(point.x + r, point.y + r); } public Rectangle getRectangle() { return rectangle; } public Color getColor() { return color; } public void setV(double vx, double vy) { this.vx = vx; this.vy = vy; } public void Move(Ball p1, double t) { this.point.x = p1.getCenterPoint().x - r + (int)(vx * t); this.point.y = p1.getCenterPoint().y - r + (int)(vy * t); } }
BezierCurve.java
package beziercurve; import java.awt.Color; import javax.swing.JFrame; public class BezierCurve { public static void main(String[] args) { JFrame frame = new JFrame(); frame.setBounds(200, 200, 640, 480); frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); PicturePanel panel = new PicturePanel(); panel.setBackground(Color.white); frame.getContentPane().add(panel); frame.setVisible(true); } }
魔方陣
奇数が入力されたときに,魔方陣を1つ生成します.
ヒンズーの連続方式(Siamese methodとも言うらしい)を用いました.
#include <stdio.h> #include <stdlib.h> void makeMagicSqu(int ***matrix, int n) { int x = n / 2, y = 0; int nextx, nexty; int cnt = 1; while( cnt <= n * n ) { if( (*matrix)[x][y] == 0 ) { (*matrix)[x][y] = cnt; cnt++; } nextx = (x + 1) % n; nexty = (n - 1) - (n - y) % n; if( (*matrix)[nextx][nexty] != 0 ) { y++; } else { x = nextx; y = nexty; } } return; } void print(int **matrix, int n) { int i, j; for( j = 0; j < n; j++ ) { for( i = 0; i < n; i++ ) { printf("%2d ", matrix[i][j]); } puts(""); } return; } void allocSquMatrix(int ***matrix, int n) { int i, j; *matrix = malloc(sizeof(int *) * n); for( i = 0; i < n; i++ ) { (*matrix)[i] = calloc(n, sizeof(int)); } return; } void freeSquMatrix(int ***matrix, int n) { int i, j; for( i = 0; i < n; i++ ) { free((*matrix)[i]); } free(*matrix); return; } int main(void) { int **matrix; int n; int i, j; printf(">"); scanf("%d", &n); allocSquMatrix(&matrix, n); makeMagicSqu(&matrix, n); print(matrix, n); freeSquMatrix(&matrix, n); return 0; }
素数判定と素因数分解
これからは日頃からプログラムを書く癖をつけようと思います.
素数判定
#include <stdio.h> int isPrime(int n) { int i; if( n < 2 ) return 0; if( n == 2 ) return 1; if( n % 2 == 0 ) return 0; for( i = 3; i * i <= n; i += 2 ) { if( n % i == 0 ) return 0; } return 1; } int main(void) { int n; for( n = 1; n <= 100; n++ ) { printf("%3d", n); if( isPrime(n) ) { printf("(素数)\n"); } else { printf("(非素数)\n"); } } return 0; }
素因数分解
"16"と入力した場合,"2*2*2*2"のように出力されます.
#include <stdio.h> #include <stdlib.h> int isPrime(int n) { int i; if( n < 2 ) return 0; if( n == 2 ) return 1; if( n % 2 == 0 ) return 0; for( i = 3; i * i <= n; i += 2 ) { if( n % i == 0 ) return 0; } return 1; } int main(void) { int *primeList; int n; int flag = 0; int i, idx; printf(">"); scanf("%d", &n); if( n == 1 ) { printf("%d\n", n); return 0; } primeList = malloc(sizeof(int) * n); primeList[0] = 2; idx = 1; for( i = 3; i <= n; i += 2 ) { if( isPrime(i) ) { primeList[idx++] = i; } } for( idx = 0; primeList[idx] <= n; ) { if( n % primeList[idx] == 0 ) { if( !flag ) { printf("%d", primeList[idx]); flag = 1; } else { printf("*%d", primeList[idx]); } n /= primeList[idx]; } else { idx++; } } free(primeList); return 0; }
Project Euler 60
ダサいです。
http://codepad.org/ZJHBDLKC
素数リストからいきなり5つ取るのではなく、
2つ取ってはそれらを組み合わせて素数にならなければ別の2つを、
3つ取ってはそれらを組み合わせて素数にならなければ別の3つを、、、
みたいにして無駄を省きました(枝刈りというのでしょうか)。