跳到主要内容

千葉大学 融合理工学府 数学情報科学専攻 数学・情報数理学コース 2019年8月実施 専門 A5

标签：

Author​

祭音Myyura (co-authored with GPT 6 Astra)

Description​

Pascal の整数型の最大値を maxint=231−1\texttt{maxint}=2^{31}-1 とし、次の型を用いる。

const MaxIndex = 999;
type bit = 0..1;
     index = 0..MaxIndex;
     bitseq = array[index] of bit;

v(b)=∑i=0999b[i]2iv(b)=\sum_{i=0}^{999}b[i]2^i とする。

(1) v(b)=0v(b)=0 のときだけ真を返す function iszero(b: bitseq): boolean; を定義せよ。(2) 0<d<maxint/20<d<\texttt{maxint}/2 とし、商を q、余りを返り値に格納する function divmod(b: bitseq; d: integer; var q: bitseq): integer; を定義せよ。(3) v(b)v(b) が3の倍数、または十進表示に3を含むときだけ真を返す function sna(b: bitseq): boolean; を定義せよ。上記関数や補助手続きを使用してよい。

题目描述​

用长度为 10001000 的小端二进制数组表示非负大整数，普通整数上界为 231−12^{31}-1。(1) 编写零判断。(2) 对小于普通整数上界一半的正除数，实现大整数除法，输出商和余数且不溢出。(3) 判断大整数是否为 33 的倍数或十进制表示含数字 33。

Kai​

(1)

function iszero(b: bitseq): boolean;
var i: integer; z: boolean;
begin
  z := true;
  for i := 0 to MaxIndex do
    if b[i] <> 0 then z := false;
  iszero := z
end;

(2) 上位桁から筆算を行う。

function divmod(b: bitseq; d: integer; var q: bitseq): integer;
var i, r, t: integer;
begin
  r := 0;
  for i := MaxIndex downto 0 do begin
    t := 2*r + b[i];
    q[i] := t div d;
    r := t mod d
  end;
  divmod := r
end;

各段階で 0≤r<d0\le r<d だから 0≤t≤2d−1<maxint0\le t\le2d-1<\texttt{maxint} でオーバーフローしない。また t<2dt<2d なので商の桁は 00 または 11。処理済み接頭部について「接頭部の値 =d×=d\times 商の接頭部の値 +r+r」が保たれるため、終了時に正しい商と余りを得る。

(3)

function sna(b: bitseq): boolean;
var q: bitseq; r: integer; hit: boolean;
begin
  r := divmod(b, 3, q);
  hit := (r = 0);
  while (not hit) and (not iszero(b)) do begin
    r := divmod(b, 10, q);
    if r = 3 then hit := true;
    b := q
  end;
  sna := hit
end;

10で割った余りは最下位の十進桁であり、商で置き換えるたびに一桁取り除かれる。00 は3の倍数なので最初の検査で真になる。

本页目录