2012/04/01(日)C# で BigInteger

はてブ数 2012/04/01 07:37 プログラミング::C#つーさ

とりあえず10進数で2300桁ぐらい扱える全然BigじゃないBigInt。負の値は扱えない。
256のとこを大きくしたら扱える桁数が増える。

割り算と剰余演算子作るのめんどくさくて作ってないけど、
たいてい必要になるのってその辺なんだよなー。もじゅろ10億7とかさー。
というわけで、longのもじゅろだけはとれるよーにしといた。

実戦で使える速度が出るかどうかは未検証。
まぁでもそういう問題は、たぶん、計算量的に無理なようにできてるでしょうね。

続きを読む

2012/04/01(日)C# で 素数表を得る。エラトステネスのふるい

はてブ数 2012/04/01 03:57 プログラミング::C#つーさ

素数表を得る

class PrimeTable {
    public List<int> Primes = new List<int>();
    public bool[] IsPrime;
    public PrimeTable(int max) {
        IsPrime = new bool[max + 1];
        for (int i = 2; i <= max; i++) IsPrime[i] = true;
        for (int i = 2; i <= max; i++)
            if (IsPrime[i]) {
                Primes.Add(i);
                for (int j = i * 2; j <= max; j += i)
                    IsPrime[j] = false;
            }
    }
}

public class Program {
    static void Main() {
        foreach (var p in new PrimeTable(100).Primes)
            Console.WriteLine(p);
    }
}

2012/03/31(土)C# で PriorityQueue を使いたいので

はてブ数 2012/03/31 22:51 プログラミング::C#つーさ

Dijkstra とか教科書通りに書きたいとき。コピペしていいプロコン用に。

public class PriorityQueue<T> {
    List<T> list = new List<T>();
    IComparer<T> comp = Comparer<T>.Default;
    class Comparer : IComparer<T> {
        Comparison<T> comparison;
        public Comparer(Comparison<T> comparison) { this.comparison = comparison; }
        public int Compare(T x, T y) { return comparison(x, y); }
    }
    public PriorityQueue() { }
    public PriorityQueue(Comparison<T> comp) { this.comp = new Comparer(comp); }
    public void Enqueue(T item) { int i = list.BinarySearch(item, comp); list.Insert(i < 0 ? ~i : i, item); }
    public T Dequeue() { T r = list[0]; list.RemoveAt(0); return r; }
    public T Peek() { return list[0]; }
    public int Count { get { return list.Count; } }
    public T this[int i] { get { return list[i]; } set { list[i] = value; } }
}

public class Program { // てすと
    class A : IComparable<A> {
        public int X;
        public A(int x) { this.X = x; }
    }

    static void Main() {
        PriorityQueue<A> Q = new PriorityQueue<A>((x, y) => y.X - x.X); // でかい順
        Q.Push(new A(1));
        Q.Push(new A(3));
        Q.Push(new A(2));
        Q.Push(new A(1));

        Console.WriteLine(Q.Pop().X);
        Console.WriteLine(Q.Pop().X);
        Console.WriteLine(Q.Pop().X);
        Console.WriteLine(Q.Pop().X);
    }
}

中の構造に単純な配列を使ってるのでPushとPopでメモリコピーが発生してO(N)なのがどうかなー。
状態数が多くなるならちゃんとヒープ作るべきなのかも。

SortedList は、キーが重複できないのでいやーんな感じ。
つーか、もうちょっとスニペットを充実させておきたいなぁ。