累乗和の公式シリーズ完全版です。べき乗和の公式の計算結果は
こちらです。見づらいし利用価値もないけれど,とりあえずネットにあげとくと頭のいい人は面白い使い道思いついたりするからね。
1.BigInteger構造体とは
たぶんべき乗和の公式よりもこっちのほうが需要ありそうなので説明します。べき乗和の方はアルゴリズムを
以前説明したのでそちらを参照してください。
BigInteger構造体はでっかい数字を扱うためのint型。int型だから整数しか扱えない。でもメモリが使えるだけ桁数を増やせる。オーバーフローしない。すごい。そんなクラスです。
ただいくつか設定をしないと使えません。コマンドプロンプトでコンパイルをしているという方は「csc -r:System.Numerics.dll *.cs」というように参照を追加します。
VisualStudioでは以下の様な参照の追加を行います。ソリューションエクスプローラーの参照から,参照の追加をクリック。
アセンブリ→フレームワーク→System.Numerics.dllにチェックを入れる。
これで準備が完了。次のプログラムを打ち込んでみる。
// コンパイル時にはSystem.Numerics.dllを参照追加すること
using System;
// BigIntegerを使うために必要
using System.Numerics;
class Program
{
static void Main()
{
// お行儀のよい宣言
BigInteger a = new BigInteger(3);
// int型からは暗黙の型変換が可能
BigInteger b = 5;
// 掛け算,割り算も普通のint型のように使える
b = 1024 * b;
// いくつかの数学関数はBigInteger構造体に用意されてる
a = BigInteger.Pow( a , 20 );
// 出力も簡単
Console.WriteLine("{0}",a);
Console.WriteLine("{0}",b);
}
}
まぁ何も気にせずに使えるということがよくわかりましたね。詳しい情報はやっぱり公式の
MSDNさんが一番だと思います。
2.プログラム
べき乗和の公式を求めるプログラムです。一応任意のべき乗数を求めることができるようになりました。100乗和の公式を求めてやるぜ!と冗談半分で言っていたのですが,何とかうまくいきました。
例えば20乗和の公式は
となることがわかります。ただ残念ながら出力結果はこんな画像にはなりません(´・ω・`)。
ちなみに今回255乗和の公式までは求めました(→
計算結果)。結構時間がかかりましたが数十分程度なのでまだまだ上は目指せそうですよ。
たいていMathematicaみたいなお高いソフト使って,誰かがこういうのは求めているものですが,1000乗和の公式とか計算したら,この世で最初に自分が計算した式かもしれない……と思うとワクワクしますね。
using System;
using System.Numerics;
class Program
{
static void Main()
{
Console.WriteLine("何乗和の公式を求めますか?");
var N = int.Parse(Console.ReadLine()) + 1;
// 係数を求める連立方程式の拡大係数行列を作る
var formula = MakeFormula(N);
// 連立方程式をガウス消去法で計算
Solve(formula, N);
// 結果を表示
Show(formula, N);
Console.WriteLine("値を代入します");
while (true)
{
Console.Write(" n = ");
var n = int.Parse(Console.ReadLine());
var f = new Fraction(0);
for (int i = 0; i < N; i++ )
f += BigInteger.Pow(n, i+1) * formula[i, N];
Console.WriteLine(f.ToString());
}
}
// 連立方程式を解くメソッド
static void Solve(Fraction[, ] formula, int N)
{
Fraction temp;
// ガウス消去法
// 前進消去
for (int i = 0; i < N; i++)
{
// まれに対角成分が0の時がある
if (formula[i, i] == 0)
{
// そういった場合は下の行から探してくる
for (int j = i + 1; j < N; j++)
{
// i行目が0でない行が見つかった場合
if (formula[j, i].ToDouble() != 0.0)
{
for (int k = i; k < N + 1; k++)
{
// 下の行から0でない値を持ってくる
formula[i, k] += formula[j, k];
}
break;
}
}
}
// 対角対角成分をを1にする
temp = formula[i, i];
for (int j = 0; j < N + 1; j++)
formula[i, j] /= temp;
// i+1行以降のi列目を0にする
for (int j = i + 1; j < N; j++)
{
temp = formula[j, i];
for (int k = 0; k < N + 1; k++)
formula[j, k] -= temp * formula[i, k];
}
}
// 後進消去
for (int i = N - 1; i >= 0; i--)
{
// 対角成分以外を0にする
for (int j = i - 1; j >= 0; j--)
{
formula[j, N] -= formula[j, i] * formula[i, N];
formula[j, i] = 0;
}
}
}
// 累乗和の公式を表示するメソッド
static void Show(Fraction[, ] d, int N)
{
Console.WriteLine("{0}乗和の公式は……", N - 1);
for (int i = 0; i < N; i++)
{
if ( d[i, N] != 0 )
{
if ( i != 0 )
Console.Write("+");
Console.Write("({0})*n^{1}", d[i, N], i + 1);
}
}
Console.WriteLine();
}
// 累乗和の公式を求める連立方程式の拡大係数行列を作るメソッド
static Fraction[, ] MakeFormula(int N)
{
var ret = new Fraction[N, N + 1];
var sum = new BigInteger(0);
for (int i = 0; i < N; i++)
{
// 係数部分を作る
for (int j = 0; j < N; j++)
ret[i, j] = BigInteger.Pow(i + 1, j + 1);
// 答えの部分を作る
sum = sum + BigInteger.Pow( i + 1, N - 1);
ret[i, N] = sum;
}
return ret;
}
}
class Fraction
{
/// <summary>
/// 分子
/// </summary>
public BigInteger Upper
{
get {
return _Upper;
}
set {
this._Upper = value;
CheckFraction();
}
}
/// <summary>
/// 分母
/// </summary>
public BigInteger Lower
{
get {
return _Lower;
}
set {
this._Lower = value;
CheckFraction();
}
}
/// <summary>
/// 分子の値を格納する変数
/// </summary>
private BigInteger _Upper;
/// <summary>
/// 分母の値を格納する変数
/// </summary>
private BigInteger _Lower;
public Fraction(BigInteger Upper, BigInteger Lower)
{
Assignment(Upper, Lower);
}
public Fraction(BigInteger n)
{
Assignment(n, 1);
}
public Fraction(int n)
{
Assignment(n, 1);
}
public Fraction(Fraction f)
{
Assignment(f.Upper, f.Lower);
}
/// <summary>
/// double型に変換するメソッド
/// </summary>
/// <returns>double型に変換した値</returns>
public double ToDouble()
{
return (double)Upper / (double)Lower;
}
/// <summary>
/// float型に変換するメソッド
/// </summary>
/// <returns>float型に変換した値</returns>
public float ToFloat()
{
return (float)Upper / (float)Lower;
}
/// <summary>
/// 約分や分母が0などのミスが無いか確認するメソッド
/// </summary>
private void CheckFraction()
{
BigInteger u = _Upper;
BigInteger l = _Lower;
BigInteger temp;
bool sign;
if (l == 0)
{
// 分母が0なのでゼロ除算の例外をぶん投げる
throw new DivideByZeroException();
} else if (u == 0)
{
// 分母が0ならばこうする
_Upper = 0;
_Lower = 1;
} else
{
// 分数の値が負ならsign = true となる
sign = l * u < 0;
// とりあえずl,uを正にする(余りの計算をするため)
l = BigInteger.Abs(l);
u = BigInteger.Abs(u);
// 常にu <= lとなるようにする
if (u > l)
{
temp = u;
u = l;
l = temp;
}
// ユークリッドの互除法
while (l % u != 0)
{
temp = l % u;
l = u;
u = temp;
}
// 約分
_Upper = BigInteger.Abs(_Upper) / u;
_Lower = BigInteger.Abs(_Lower) / u;
// 正負を直す
if (sign)
_Upper = -_Upper;
}
}
/// <summary>
/// クラス内で代入を行うメソッド(ただしCheckFractonから呼んではならない)
/// </summary>
/// <param name="Upper">分母</param>
/// <param name="Lower">分子</param>
private void Assignment(BigInteger Upper, BigInteger Lower)
{
this._Upper = Upper;
this._Lower = Lower;
CheckFraction();
}
public static Fraction operator +(Fraction left, Fraction right)
{
BigInteger l = left.Lower * right.Lower;
BigInteger u = left.Upper * right.Lower + right.Upper * left.Lower;
return new Fraction(u, l);
}
public static Fraction operator -(Fraction left, Fraction right)
{
BigInteger l = left.Lower * right.Lower;
BigInteger u = left.Upper * right.Lower - right.Upper * left.Lower;
return new Fraction(u, l);
}
public static Fraction operator *(Fraction left, Fraction right)
{
BigInteger l = left.Lower * right.Lower;
BigInteger u = left.Upper * right.Upper;
return new Fraction(u, l);
}
public static Fraction operator /(Fraction left, Fraction right)
{
// 逆数にする(0除算ならここで例外が発生する)
right = new Fraction(right.Lower, right.Upper);
return right * left;
}
public static Fraction operator /(Fraction f, int n)
{
return new Fraction(f.Upper, f.Lower * n);
}
public static Fraction operator *(Fraction f, int n)
{
return new Fraction(f.Upper * n, f.Lower);
}
public static implicit operator Fraction(BigInteger n)
{
return new Fraction(n);
}
public static implicit operator Fraction(int n)
{
return new Fraction(n);
}
public static bool operator <(Fraction left, Fraction right)
{
return left.ToDouble() < right.ToDouble();
}
public static bool operator >(Fraction left, Fraction right)
{
return left.ToDouble() > right.ToDouble();
}
public static bool operator <=(Fraction left, Fraction right)
{
return left.ToDouble() <= right.ToDouble();
}
public static bool operator >=(Fraction left, Fraction right)
{
return left.ToDouble() >= right.ToDouble();
}
public static implicit operator double (Fraction f)
{
return f.ToDouble();
}
public static implicit operator float (Fraction f)
{
return f.ToFloat();
}
public static bool operator ==(Fraction left, Fraction right)
{
// nullかどうかは分子があるかどうかで判断する
if (left.Upper == null || right.Upper == null)
return false;
return left.Upper == right.Upper && left.Lower == right.Lower;
}
public static bool operator ==(Fraction left, int n)
{
Fraction right = new Fraction(n);
// nullかどうかは分子があるかどうかで判断する
if (left.Upper == null || right.Upper == null)
return false;
return left.Upper == right.Upper && left.Lower == right.Lower ;
}
public static bool operator !=(Fraction left, int n)
{
Fraction right = new Fraction(n);
return !(left == right);
}
public static bool operator !=(Fraction left, Fraction right)
{
return !(left == right);
}
public override bool Equals(object obj)
{
if (obj == null || this.GetType() != obj.GetType())
return false;
return (this == (Fraction)obj);
}
public override int GetHashCode()
{
return (int)((this.Upper * this.Lower) % int.MaxValue);
}
public override string ToString()
{
if ( this.Upper == 0 )
return String.Format("0");
else if ( this.Lower == 1 )
return String.Format("{0}", this.Upper);
return String.Format("{0}/{1}", this.Upper, this.Lower);
}
}