Project Euler 62

Project Euler

13, 23, 33, ... の立方数の各桁の数字をカウントしたとき，
0~9の個数が同じになる立方数は，互いに桁の置き換えを持つ立方数であることに気付きました．

0の個数ごとに枝分かれをし，そのそれぞれのノードから，1の個数ごとに枝分かれをし，...
という多分木を作ることで，ある立方数について各桁の数字のカウント値によってその木を手繰ることを考えると，
同じ葉に行き着く立方数は，最初の説明より，互いに桁の置き換えを持つ立方数だと分かります．
そして同じ葉に行き着く立方数が5つ現れたとき，最初にその葉に行き着いた立方数がこの問題の答えになります．

http://codepad.org/nWli4yR6

(50msで答えを求められるのですが，早すぎて自分でも驚いています)

ベジエ曲線

以下のプログラムは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);
    }    
}

魔方陣

C言語基礎

奇数が入力されたときに，魔方陣を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

Project Euler

ダサいです。
http://codepad.org/ZJHBDLKC

素数リストからいきなり5つ取るのではなく、
2つ取ってはそれらを組み合わせて素数にならなければ別の2つを、
3つ取ってはそれらを組み合わせて素数にならなければ別の3つを、、、
みたいにして無駄を省きました(枝刈りというのでしょうか)。

Project Euler 59

Project Euler

問題文がわかりづらいですね・・・ｗ
暗号鍵の1文字と暗号文の1文字でxorをとるようですね。

何をもって完璧に復号できたか、ですが、
復号した文中に"the"や"can"があるとかは判定せず、その文が
英単語、数字、英文で使われそうな記号(具体的には、. , : ; ? ! ' ( ))で構成されているかどうかを
判定することにしました。

http://codepad.org/gg0exCf4