求“超长整数求余”的算法实现。100分。

Question

函数框架，请大家完善中间的代码： 
function LongIntMod(p_strNum:string; p_intMod:Integer):Integer;
{ 
} p_strNum是全整数的字符串，不包含小数。 
p_strNum之所以使用字符型，是因为数字非常长，是上百位或者上千位甚至更长的数字字符串。 由于运算量很大，大家考虑一下运算效率。

Answer 1

TO:bdmh
我们这个是工程上的，不仅仅是上百位，上万位长的数字都有。TO:kfcoffe
我们要求的这个功能其实和mod函数的功能是一模一样的，仅仅是输入数字为字符串，一点也不模糊呀。

Answer 2

每19位转化成int64，或者每9位转化成int,求余。

Answer 3

TO:kfcoffe
mod是不能满足的，我们的数字是很长的，即使是用int64也会溢出的。
除数倒是在integer范围内，一般为618,有时又取62。

Answer 4

TO:lhylhy
你的方法是可以考虑的，谢谢。
不过如果我的数很长，上万位的情况下，这个处理办法会很慢的。

Answer 5

搞定了，自己测试去吧
const
  p_intMod = 34;
  intLen = 3;
  interval = 1000;procedure TForm1.Button1Click(Sender: TObject);
var
  p_strNum: string;
  ret, vstr, tmpStr: string;
  index: Integer;
  tmpMod: Integer;
  len8: Integer;
begin
  p_strNum := Edit1.Text;
  vstr := rightstr(p_strNum, intLen);
  tmpStr := LeftStr(p_strNum, Length(p_strNum)-intLen);
  index := 1;
  tmpMod := 0;
  while vstr <> '' do
  begin
    len8 := StrToInt(vstr);
    if index > 1 then
      tmpMod := tmpMod + ((len8 mod p_intMod) * Nmod(index-1)) mod p_intMod
    else
      tmpMod := len8 mod p_intMod;
    Inc(index);
    tmpMod := tmpMod mod p_intMod;
    vstr := rightstr(tmpStr, intLen);
    tmpStr := LeftStr(tmpStr, Length(tmpStr)-intLen);
  end;  edit2.Text := IntToStr(tmpMod);
end;function TForm1.Nmod(n: Integer): Integer;var
  i: integer;
begin
  result := 0;
  if n >= 1 then
  begin
    if n = 1 then
      result := interval  mod p_intMod
    else
      result := (Nmod(n-1) * Nmod(1)) mod p_intMod;
  end;
end;

Answer 6

其中这两个值就是截断，必须设置一致
  intLen = 3;
  interval = 1000;  //有intLen个0

Answer 7

TO:ok1411这个参数interval，是做什么用的？

Answer 8

自己看啊，哪里用到了
就是截取时不是留下来的，如123456，截取成123 × 1000 + 456, interval就是这里的1000

Answer 9

这是3位一取，如4位一取，就成了12 × 10000 + 3456
整数取的话应该可以8位一取，int64应该可以16位吧

Answer 10

除数大概是多大的？
建议还是用mod，怎么利用的话就是看mod支持的最大数值多少，然后将你的数字从高到低分段，段的大小控制下，mod除数，（余数*分段大小+第二段）mod除数循环下应该可以解决问题

Answer 11

从右往左,不如从左往右算,步长尽可能在integer范围内设置最大

Answer 12

其实这里用递归，每次都去执行效率浪费了一点，可以一开始就把用到的计算出来放到一个数组里面就行了；
function TForm1.Nmod(n: Integer): Integer;
var
  i: integer;
begin
  result := 0;
  if n >= 1 then
  begin
    if n = 1 then
      result := interval  mod p_intMod
    else
      result := (Nmod(n-1) * Nmod(1)) mod p_intMod;
  end;
end;

Answer 13

用的就是我们平时手工计算时的竖式除法的算法:function GetInt(sNum: String;  h, t: Integer): Integer;
//功能描述: 取出sNum中第h到第t个部分的整数
begin
  Result := 0;
  while (h <= t) and (h <= Length(sNum)) do
  begin
    Result := Result * 10 + ord(sNum[h]) - ord('0');
    inc (h);
  end;
end;function PutInt(var sNum: String;  n, t: Integer): Integer;
//功能描述: 将整数n从第t个数字开始往前填写到sNum中, 函数返回值为最右边的填写位置
begin
  repeat
    sNum[t] := chr(n mod 10 + ord('0'));
    dec(t);
    n := n div 10;
  until (n = 0) or (t < 1);
  Result := t + 1;
end;function LongIntMod(p_strNum:string;  p_intMod:Integer): Integer;
var
  h, t, n: Integer;
begin
  Result := 0;
  h := 1;
  t := 1;
  while t <= Length(p_strNum) do
  begin
    //从p_strNum中取出够p_intMod除的部分
    n := GetInt(p_strNum, h, t);
    while (t <= Length(p_strNum)) and (n < p_intMod) do
    begin
      inc(t);
      n := GetInt(p_strNum, h, t);
    end;
    if n < p_intMod then
    begin
      Result := n;
      break;
    end
    else begin
      //将取出的部分除以p_intMod之后的余数填回p_strNum后继续进行计算
      h := PutInt(p_strNum,  n mod p_intMod, t);
      t := h;
    end;
  end;
end;//调用的例子:
  ShowMessage (IntToStr(LongIntMod('111111111111111111111111111111111111111111111111111', 23)));

Answer 14

因为算法中没有用到字符串的连接运算这类耗时操作, 所以速度还是可以接受的。可以测试一下下面这个被除数为10万位, 除数为6位整数的例子：procedure TForm1.FormCreate(Sender: TObject);
var
  i : integer;
  s : String;
begin
  s := '';
  for i := 1 to 10000 do
    s := s + '1234567890';
  ShowMessage ('Press [OK] to start...');
  ShowMessage (IntToStr(LongIntMod(s, 123456)));
  Application.Terminate;
end;