2020-06-07

桁数の大きい数字どうしの割り算を暗算する方法

桁数の大きい数字どうしの割り算を暗算する現実的な方法を思いついたので紹介します。筆者はこの方法で60桁÷30桁の暗算に成功しました。この方法は桁数の大きい数どうしの掛け算をする方法と関わりが深いのでまずはこちらの記事を読んだ方が良いかもしれません。

桁数の大きい数字どうしの掛け算を暗算する方法 - itleigns’s diary

はじめに

掛け算と同じですがこの記事で言う暗算は答え以外の数字を何も記入しないで問題を解くということです。問題文を覚えないので暗算中に問題文を見る必要があります。答えも全部は覚えないので計算した部分を出力して別の部分を計算するを繰り返します。また出力した答えの一部も他の部分を計算するときに見ます。またこちらは割り算のみに関してですがこの方法は全ての場合に対応できるわけではありません。割られる数が割る数で割り切れないといけないし割る数の値が0でない1番下の位が1,3,7,9のいずれかでないといけません。

前提

上で挙げた4つの数1,3,7,9と0,1,...,9を掛けた数を見てみましょう。以下のようになります。

	1	2	3	4	5	6	7	8	9
1	1	2	3	4	5	6	7	8	9
3	3	6	9	12	15	18	21	24	27
7	7	14	21	28	35	42	49	56	63
9	9	18	27	36	45	54	63	72	81

行ごとに1の位が0,1,...,9なものが丁度1つずつあることが分かります。この性質を使っていきます。

方法

まず割られる数を $A$ 割る数を $B$ とします。上でも述べた通り $A$ が $B$ の倍数で $B$ の値が0でない1番下の位が1,3,7,9の場合のみを考えます。

$A$ が $B$ の倍数のときを考えているので $B$ の末尾にある0の数だけ $A$ の末尾に0があります。 $A$ , $B$ の末尾から0を同じ数だけ取り除いても答えが変わらないので $B$ の末尾にある0の数だけ $A$ , $B$ の末尾から0を取り除きます(つまりないものとみなして計算します。)。そうすると $B$ は1の位が1,3,7,9のいずれかになるので以下この場合のみを考えます。

まず6桁÷3桁の割り算で例を示します。掛け算とやっていることはほとんど同じなので掛け算に対応させて $A$ が679841で $B$ が797の場合を計算してみます。答えを $C$ とすると $C$ の桁数は(6-3+1)以下なので $C=c_3c_2c_1c_0$ と書けます。

f:id:itleigns:20200606172142p:plain:w500

上の式を満たすように $c_3c_2c_1c_0$ を決めていきます。まず $B$ の1の位と $C$ の1の位の積の1の位が $A$ の1の位になるように $C$ の1の位を決めます。7 × 3 = 21なので $c_0$ は3に決まります。後で使うので21を10で割った商の2を覚えておきます。

f:id:itleigns:20200606182632p:plain:w500

覚えておいた2と $B$ の10の位と $C$ の1の位の積と $B$ の1の位と $C$ の10の位の積の和の1の位が $A$ の10の位になるように $C$ の10の位を決めます。2 + 9 × 3 + 7 × 5 = 64なので $c_1$ は5に決まります。後で使うので64を10で割った商の6を覚えておきます。

f:id:itleigns:20200606184235p:plain:w500

覚えておいた6と $B$ の100の位と $C$ の1の位の積と $B$ の10の位と $C$ の10の位と $B$ の1の位と $C$ の100の位の積の和の1の位が $A$ の100の位になるように $C$ の100の位を決めます。6 + 7 × 3 + 9 × 5 + 7 × 8 = 128なので $c_2$ は8に決まります。後で使うので128を10で割った商の12を覚えておきます。

f:id:itleigns:20200606214258p:plain:w500

覚えておいた12と $B$ の100の位と $C$ の10の位の積と $B$ の10の位と $C$ の100の位の積と $B$ の1の位と $C$ の1000の位の積の和の1の位が $A$ の1000の位になるように $C$ の1000の位を決めます。12 + 7 × 5 + 9 × 8 + 7 × 0 = 119なので $c_3$ は0に決まります(この場合答えが3桁ということなので0は出力しません)。

f:id:itleigns:20200606213915p:plain:w500

このように答えの853が求まりました。だいたいイメージはつかめましたでしょうか？疑似コードにしてみるとこのようになります。ただし $find(a,b,c)$ はa + b × dの1の位がcになる0,1,...,9の数dを返します。

入力
$a_{n-1}a_{n-2}\cdots a_0$
$b_{m-1}b_{m-2}\cdots b_0$
出力
$a_{n-1}a_{n-2}\cdots a_1a_0 \ / \ b_{m-1}b_{m-2}\cdots b_1b_0$
アルゴリズム
$S := 0$
$for \ \ i = 0\cdots n-m$
　　　 $for \ \ j = max(0,i-m+1)\cdots i-1$
　　　　　　 $S \ := \ S \ + \ c_j \times b_{i-j}$
　　　 $c_i \ := \ find(S,b_0,a_i)$
　　　 $S \ := \ S \ + \ c_i \times b_0$
　　　 $S \ := \ S \ / \ 10$
$if \ \ c_{n-m} \ == \ 0$
　　　 $return \ c_{n-m-1}c_{n-m-2}\cdots c_0$
$else$
　　　 $return \ c_{n-m}c_{n-m-1}\cdots c_0$

考察

掛け算のときと同様の議論でこの方法で200桁÷100桁の割り算を4桁の数字を1つ覚えておくだけでできます。この方法では $a_{n-1},a_{n-2},\cdots ,a_{n-m+1}$ の情報を使っていませんが $A$ が $B$ で割り切れるという条件があるので計算できます。10進法でなく $p$ 進法( $p$ は素数)なら割り切れる場合は常に計算できたのにと思います。今回扱ってないケースはおそらく下の桁から計算することができないので暗算可能だと思いますがかなり難しくなると思います。必要な演算の量は $4m$ 倍（うまく不等式を作れば4倍くらいでできるかも）でしかも作業が複雑になると思います。

最後に

実際にこの方法で60桁÷30桁の暗算をやってみた動画です。

youtu.be

2019-09-06

桁数の大きい数字どうしの掛け算を暗算する方法

桁数の大きい数字どうしの掛け算を暗算するにはたくさんの数字を記憶しないといけないからできないと思っている人はいないでしょうか？今回は3~4桁の数字を1つ覚えておくだけで大きい数字どうしの掛け算を暗算する方法を紹介します。筆者はこの方法で20桁×20桁の掛け算に成功しました。

はじめに

この記事で言う暗算は答え以外の数字を何も記入しないで問題を解くということです。問題文を覚えないので暗算中に問題文を見る必要があります。答えも全部は覚えないので計算した部分を出力して別の部分を計算するを繰り返します。

方法

まず3桁×3桁の掛け算で例を示します。797×853を計算します。

まずは1の位と1の位を掛けます。7×3は21です。21を10で割った余りの1を答えの1の位に書きます。商の2は覚えておきます。

次に10の位と1の位、1の位と10の位を掛けたものを覚えておいた2に足します。2+9×3+7×5で64となります。10で割った余りの4を10の位に書き商の6を覚えておきます。

次に100の位と1の位、10の位と10の位、1の位と100の位を掛けたものを覚えておいた6に足します。6+7×3+9×5+7×8で128となります。10で割った余りの8を100の位に書き商の12を覚えておきます。

次に100の位と10の位、10の位と100の位を掛けたものを覚えておいた12に足します。12+7×5+9×8で119となります。10で割った余りの9を1000の位に書き商の11を覚えておきます。

最後に100の位と100の位を掛けたものを覚えておいた11に足します。11+7×8で67となります。100000の位に6を10000のくらいに7を書き終わりです。

f:id:itleigns:20190905170624j:plain

このように797×853を計算できました。だいたいイメージはつかめましたでしょうか？疑似コードにしてみるとこのようになります。

入力 


出力

アルゴリズム

これは下の桁から順番に出力するアルゴリズムですが正しい答えを出力します。

アルゴリズムの考察

この計算方法を使うと大きな数どうしの掛け算を暗算することが現実的になります。しかし上の疑似コードでの $S$ が大きな数になりすぎると難しいでしょう。この $S$ がどのくらいの値まで大きくなるか解析しましょう。上の疑似コードで $i=p$ で $S$ に足される数を $S_p$ とすると

$\displaystyle S_p = \sum_{j=max(0,p-m+1)}^{min(p,n-1)} a_jb_{p-j} \leq 81min(n,m)$

です。より $i=p$ での計算が終わった時の $S$ の値は

$\displaystyle \sum_{i=0}^p 10^{-p+i}S_p \leq \sum_{i=0}^p10^{-p+i}\cdot 81min(n,m)\leq 90min(n,m)$

です。より100桁×100桁の掛け算までは4桁の数字を1つ覚えておくだけでできます。

おまけ

実際にこの方法で20桁×20桁の掛け算をやってみた動画です。

youtu.be

(2020-6-7追記)

この方法は海外では有名でCriss-Cross Methodと呼ばれているそうです。

Criss-Cross Method of Multiplication

割り算もやってみました。

桁数の大きい数字どうしの割り算を暗算する方法 - itleigns’s diary

2017-07-25

ピクミン樹海のへそ 1日クリア

樹海のへそを1日クリアしたので流れを記録しておきます.

85匹の赤ピクミンと15匹の黄ピクミンを花ピクミンにして前日までに用意しておきました.

赤ピクミンを85匹オニオンから出す.
黄ピクミンを15匹オニオンから出す.
白い岩の壁の左の間欠泉のあるところに降りついてきたピクミンで間欠泉を掘る.
ピクミンが全員ついてくるのをマップで確認しながら降りてブタドックリの前に行く.
ブタドックリがオリマーの方を向いたらCスティックでブタドックリを80匹くらいで倒す.
ブタドックリを倒している間残りのピクミンで4匹のトビンコを倒す.
倒し終わったら水辺の方のブタドックリをCスティックで80匹くらいで倒す.
残りのピクミンでペレットを取ったパンモドキにダメージを与え持っているペレットに赤ピクミンを2匹付けパンモドキと取り合わせる.
グラビティジャンパーのある方へ行きピクミンを解散させる.
赤ピクミンを全員呼びスローブに投げスローブをかけさせる.
黄ピクミンを全員呼びスローブの右にある高い場所に投げる.
間欠泉で上がり黄ピクミンを全員呼び爆弾岩を取らせる.
爆弾岩を取った黄ピクミンは高台に投げる.
全員投げたら間欠泉で上がりスローブの近くでフリーピクミンになってるピクミンを呼び多すぎる分をスローブに投げることで隊列を29匹にする.(グラビティジャンパーを早く回収したくてダマグモ戦で多くピクミンを使いたくてこの配分がちょうどよかった.)
29匹をグラビティジャンパーの近くで解散させパーツをピクミンが運び出すまでに爆弾岩を持った15匹の黄ピクミンを触れて回収させる.
グラビティジャンパーを運んでいるピクミンを追い抜かしスローブをかけ終えた赤ピクミンを回収する.
隊列が69匹になるのでダマグモの方に行く.途中マロガエルがいるのでグラビティジャンパーのあった場所の方向に一度誘き寄せておく.
ダマグモの前の白い岩の壁を壊す.
赤ピクミンを全員呼びボケナメコを倒しに行く.
ボケナメコの近くでピクミンを解散させボケナメコを転倒させ赤ピクミンを30匹投げ残りは解散させる.
ボケナメコを倒したら隊列が30匹になるのでパーツにCスティックで30匹全員付ける.
残りの24匹を連れてダマグモを倒しに行く.
ダマグモのいるエリアに入ったら降ってくるダマグモに潰されないようにCスティックを前に倒しておく.前に進みながら適切なタイミングで人指し指でAボタンを連打する.(タイミングは練習して覚えるしかない.)ダマグモに数匹ピクミンが付いたら親指でAボタンを押し残りのピクミンを頭が下がってるダマグモに付ける.(時々ダマグモすぐには降ってこないことがあるがその時は音楽に合わせて適切なタイミングまた適切な位置でピクミンを投げる.)振り払われたピクミンや頭につかなかったピクミンを頭についてるピクミンを呼ばないようにしながら呼び頭に投げるを繰り返す.(今回の挑戦でピクミンが2匹死んだ.またダマグモはすぐに降ってきた.)
今回の挑戦ではダマグモを倒したあたりで4分の1の鐘が鳴った.
20匹より多い分のピクミンを別の場所に投げておいて20匹でガードサテライトを回収.
残りの赤ピクミンと黄ピクミンを連れ宇宙船の近くの間欠泉の方へ行く.
上に上がる前にピクミンを解散させ爆弾岩を持ったピクミンだけで上がる.
白い岩の壁を壊す.(この辺でグラビティジャンパーが回収される.)
黄オニヨンに運ばれるようにパンモドキを運ぶ.
グラビティジャンパーを回収していたピクミンを呼びスペースフロートを回収させる.
パンモドキもスペースフロートも回収させるぎりぎりのところで呼ぶ.
赤ピクミン3匹を赤オニヨン近くの白い壁に投げる.
地上に存在するピクミンの数が93匹になるように赤ピクミンを数匹オニヨンに戻す.
リブラとアナログコンピュータのある方面の黒い土の壁の方に行く.途中解散させておいたピクミンを呼び隊列を45匹にする.
ブタドックリの火に当たらないぎりぎりの場所でピクミンを解散させ残りの爆弾岩で(通常は3個)黒い土の壁を壊す.壊し切れないので赤ピクミン25匹で残りを破壊させる.
黄ピクミン15匹を連れ青オニヨンの方に行く.途中で青オニヨンに近い方のブタドックリを黄ピクミンで回収させる.水辺に入る前にブタドックリを回収していない黄ピクミンを溺れないように解散させておく.
青オニヨンに近づき青オニヨンが種を吹いたら解散させておいた黄ピクミンとブタドックリを持った黄ピクミンを呼びオートマチック・ギアにつながる枝に黄ピクミン15匹を投げる.
青ピクミンが引き抜ける状態になっているので引き抜く.
青オニヨンの右のペレット草に抜いたピクミンをぶつけて回収させる.
その隙に左のペレット草をオリマーパンチで倒し回収し終わったピクミンを呼び解散し回収させる.(今回の挑戦ではここでオメガスタビライザーが回収されたので運が良かった.(ピクミンがすぐに引き抜けるようになる.))
回収し終わったピクミンに後ろのペレット草のペレットの1つを回収させる.(落ちてくるオートマチック・ギアを視界に映さないように注意.)
4匹の青ピクミンを抜く.
回収し終わったピクミンと合わせて5匹で5ペレットを運ばせる.(今回の挑戦ではここでスペースフロートが回収されたので運が良かった.)
青ピクミンを2匹抜き後ろのペレット2つを回収させる.
赤オニヨンの方に行きオメガスタビライザーの回収を終えた赤ピクミンを呼び4匹オニヨンに戻し残りに赤オニヨン近くの白い土の壁を壊させる.
青オニヨンに戻りトビンコ4匹と近くのブタドックリを回収させる.(今回の挑戦ではここで昼の鐘が鳴った.)
リブラとアナログコンピュータ方面の黒い土の壁を壊し終えた赤ピクミンを回収しリブラの橋をかけさせる.
赤オニヨンに戻りオートマチックギアとガードサテライトを回収し終えたピクミンを呼び赤ピクミンは全員オニヨンに戻す.(蕾ピクミンや葉ピクミンがいるからこちらを優先的に戻す.)
黄ピクミンに白い土の壁を壊すのを手伝わせる.
壁が壊れたら全員呼び赤ピクミンを9匹オニヨンに戻す.
残りのピクミンを連れて青オニヨンの方へ行く.途中赤ピクミンや黄ピクミンが水辺に落ちないように解散させる.
青ピクミンを29匹オニヨンから呼びフリーピクミン11匹呼ぶ.
白い土の壁があったところの近くの蜜の出る小石の方へ行く.途中解散させた赤ピクミンと黄ピクミンを呼ぶ.
赤ピクミンか黄ピクミンが5匹小石についているようにして青ピクミン全員が小石の周りにいるようにしてCスティックを回し全員花ピクミンにする.
75匹を連れリブラの橋の方に行く.
広い場所で解散し黄ピクミン全員と青ピクミンを0~20匹を橋をかけてるピクミンに手伝わせる.(今回の挑戦では12匹の青ピクミンが橋に向かった.)
残りのピクミンを全員呼びアナログコンピュータの方に行く.解散しアナログコンピュータを青全員で回収させる.
赤ピクミンを呼びアナログコンピュータが上がってくる場所にCステイックで赤ピクミンを集めCスティックを放す.
アナログコンピュータが陸に上がったら青ピクミンを1度の笛で全員呼びその直後に解散する.(呼んだ直後のピクミンは解散しないので青ピクミンのみが隊列に残る.)
青ピクミンを全員を連れリブラの橋の方へ行く.(今回の挑戦では橋を渡っている途中に4分の3の鐘が鳴り橋が完成した.)
連れている青ピクミンで間欠泉を掘らせる.
フリーピクミンを全員呼び間欠泉が掘り終わったタイミングで解散.
黄ピクミンを15匹呼び高台に投げる.
間欠泉で上がり黄ピクミンを呼ぶ.
黄ピクミンでリブラを回収.
降りて青ピクミンを全員呼び橋の方に連れて行き解散する.
赤ピクミンを呼び15匹になるように調整.(今回の挑戦では1度呼んだだけで15匹になった.)
降りてくるリブラをアナログコンピュータと同様の方法で赤ピクミンに運ばせ黄ピクミンを回収する.
全員を連れて初めに倒したブタドックリのいた方へ行く.(今回の挑戦ではアナログコンピュータを間欠炎のある地帯で抜かせたので(初めて)滞りなく出来た.)
死骸やペレットを回収しないように解散し青ピクミン40匹を呼ぶ.
ノンダイオキシンの近くのラムネ瓶に行きマロガエル2匹を引き寄せる.
マロガエル2匹が1度跳んだらノンダイオキシンの近くでピクミンを解散させ回収させる.
ノンダイオキシンを視界から外した後,更にマロガエルを遠くにおびき寄せる.
グラビティジャンパーのあった場所の近くのマロガエルもグラビティジャンパーのあった方におびき寄せておく.
解散させておいた赤ピクミンと黄ピクミンを呼び陸地に上がったノンダイオキシンから青ピクミンを数匹剥がし赤ピクミンと黄ピクミンを付ける.
残りの青ピクミンでイオニウムジェット1を回収させる.(今回の挑戦では回収させた少し後ででもうすぐ日没ですの表示がでた.この時点で解散させたピクミンが3匹アナログコンピュータに付いたのでアナログコンピュータに23匹リブラに15匹ノンダイオキシンに40匹イオニウムジェット1に22匹で運んだいた.)
アナログコンピュータとリブラの回収を終えたピクミンにノンダイオキシンを手伝いに行かせる.
あとは待つだけ.

全回収した時4カウントくらい残ってた.

2017-05-26

ピクミン希望の森チャレンジモード

全回収したのでチャートを書きます。

赤ピクミン3匹抜く
近くの赤の1ペレットを3つ取る
青ピクミン3匹抜く
近くの青の1ペレットを3つ取る
黄ピクミン3匹抜く
近くの黄の5ペレットを取る
赤ピクミンを何匹か抜く
近くの赤の5ペレットを取る
青ピクミンを何匹か抜く
近くの青の5ペレットを取る
ペレットが回収されている間適当にピクミンを何匹か抜く
抜いたピクミンを全員集めて本編で岩の壁がある方に行く
コチャピーを2匹,チビクマを3匹,ペレット草を2つ倒し回収する
ピクミンを全部抜く
本編で土の壁がある方に行き小チャッピーを4匹倒す
近くのチビクマを2匹倒す
近くのチャッピーを倒す
近くの赤の1ペレットを3つ運ぶ
近くのチャッピーを倒し赤に回収されるように運ぶ
水の方に行き青ピクミンだけを連れて橋に3匹投げ1ペレットを2つ10ペレットを1つ運ぶ
チビクマ2匹とチャッピーを回収する
橋の方に行き橋にピクミン1匹投げ小チャッピー2匹を倒し回収
ペレット草を倒し黄が出れば回収しそうでないなら手持ちのピクミンの色を考え速く回収できそうなら回収しそうでないなら放っておく
チビクマを倒し回収する
ピクミンが余っていれば小チャッピー4匹を回収
ピクミンを全部抜く
草の方に行きピクミンをできる限り花にする
ピクミンを全員連れて岩の壁方面に行く
スロープに3匹投げる
近くのチャッピーを倒す
本編のただものでないネジのある方向に行きチビクマ1匹とコチャッピー2匹を倒す
ペレット草2つとチビクマを倒し1ペレットは回収する
クマチャッピーを倒しクマチャッピーと赤の10ペレットを回収
小チャッピーを倒し回収
戻りながらチビクマ,黄の10ペレット,赤の20ペレット,コチャッピー2匹,コクマチャッピー1匹をこの順で運び残りのピクミンで20ペレットを手伝わせる
オニオンに戻り回収を終えたピクミンを集めペレットを集めてるピクミンを手伝わせる
ペレットの回収が終われば全てのピクミンを集め再度岩の壁方面に行く
水のある方に行き黄の5ペレット青の5ペレットを回収し小チャッピーを倒す
チャッピーとチビクマ2匹をを倒し死骸と黄の1ペレット3つを回収,この時黄ピクミンが残らないようにする
段差の上にピクミンを全て投げる
小チャッピー4匹とクマチャッピーを倒す
青の10ペレットとクマチャッピーを回収しコチャッピーを4匹回収
オニヨンの方に戻りながら回収されてなければ1ペレットと小チャッピーを回収
ピクミンを全員連れて本編のヘビガラス方面に行く
黄ピクミンに爆弾を全て回収させ岩の壁を壊す
コチャッピー3匹とチャッピーを爆弾を使わずに倒し青ピクミンで箱を動かす
20の青ペレットと死骸をすべて運ぶ.このときできるだけ黄色を使うようにする
箱のあった所を渡りチャッピー,クマチャッピー,ヤマシンジュを爆弾で倒す.ここで爆弾が1つになる
死体をできるだけ青で回収させ(水辺を通って早く回収してもらいたいから)オニヨンに戻る
回収を終えているピクミンから黄色を多く含め20匹くらい呼ぶ
橋ができ上がっているので20ペレットと5ペレットを運ばせる.
残りのピクミンと回収を終えたピクミンを呼び本編のフタクチドックリのいる方に行く
爆弾を回収し壁を壊しチャッピー2匹とクマチャッピー,ヤマシンジュを倒しスローブの下のチャッピーとともに回収

2017-05-20

根付き木で頂点uが頂点vの子孫かを<O(n),O(1)>で判定

調べても見つからなかったので書きました.

根からdfsを行い通った順に頂点に番号を付けて配列fにメモする.
すると全ての頂点vに対してその頂点の子孫uはvの直後に続けて番号付けられる.
だからそれぞれの頂点vに対しどこまでがvの子孫かを配列tにメモする.
f[v]≦f[u]≦t[v]かどうかでuがvの子孫か求められる.

C#で書いたソースコードは以下.

public class TreeAncestor{
    //根付き木
    List<int>[] G;
    int count;
    int[] eulerf;
    int[] eulert;
    //vは根でG0は木
    public TreeAncestor(int v,List<int>[] G0){
        G = G0;
        count = 0;
        eulerf = new int[G.Length];
        eulert = new int[G.Length];
        dfs(v,-1);
    }
    void dfs(int v,int f){
        //付けた番号をメモする.
        eulerf[v] = count;
        count++;
        for(int i=0;i<G[v].Count;i++){
            int t = G[v][i];
            if(t != f){
                dfs(t,v);
            }
        }
        //どこまでがvの子孫かメモする.
        eulert[v] = count;
    }
    //uはvの子孫か判定.
    public bool Ancestor(int v,int u){
        return eulerf[v] <= eulerf[u] && eulerf[u] <= eulert[v];
    }
}

	1	2	3	4	5	6	7	8	9
1	1	2	3	4	5	6	7	8	9
3	3	6	9	12	15	18	21	24	27
7	7	14	21	28	35	42	49	56	63
9	9	18	27	36	45	54	63	72	81

	1	2	3	4	5	6	7	8	9
1	1	2	3	4	5	6	7	8	9
3	3	6	9	12	15	18	21	24	27
7	7	14	21	28	35	42	49	56	63
9	9	18	27	36	45	54	63	72	81

	1	2	3	4	5	6	7	8	9
1	1	2	3	4	5	6	7	8	9
3	3	6	9	12	15	18	21	24	27
7	7	14	21	28	35	42	49	56	63
9	9	18	27	36	45	54	63	72	81