Download presentation
Presentation is loading. Please wait.
1
Problem A: Radix 3
2
問題概要 十進数の数値を、変則的な三進数で表す 一般的な三進数 : (2, 1, 0 が使える)
11 = 32× × ×2 = (102)3 変則三進数 (GSC) : (1, 0, -1 が使える) 11 = 32× × ×(-1) = (11-)GSC
3
ただの三進数なら 11 mod 3 = 2 3 mod 3 = 0 1 mod 3 = 1 11 / 3 = 3 3 / 3 = 1
1 / 3 = ⇒ 終了 A: (1 0 2)3
4
これでもほとんど同じ 11 mod 3 = 2 4 mod 3 = 1 1 mod 3 = 1 11 / 3 = 3 4 / 3 = 1
1 / 3 = ⇒ 終了 A: (1 1 - )GSC +1
5
負数のときは? (-11) mod 3 = -2 (-4) mod 3 = -1 (-1) mod 3 = 0 (-11) / 3 = -3
(-4) / 3 = -1 (-1) mod 3 = 0 (-1) / 3 = ⇒ 終了 A: ( )GSC -1
6
ただし! 非除数が負の「除算」・「剰余算」の結果は ANSI C では実は不定 (CPU・処理系に依存) 関数 div()
#include <stdlib.h> div_t div(int num, int denom); typedef struct div_t { int quot; /* 商 */ int rem; /* 剰余 */ };
7
負数のときは? (2) ...と、まじめにやってもよいが、 ぶっちゃけ 8 = (1 0 - )GSC -8 = ( - 0 1 )GSC
‘1’ を ‘-’ に ‘-’ を ‘1’ に、するだけ
8
ただし! (2) 今回の値の範囲は まあ、一般的な符号付整数の範囲ですが... それは実は (-231) ～ (231-1)
負数を整数に直して、 -(-231) = 231 : オーバーフロー! ってなことにはならないように...
9
出典 South Africa Regional Contest, 2002 Problem 1: Radix 3
Similar presentations
