【基础题目】A%B Problem

题目描述

C–语言是一种C的简化版，它仅有的三种运算符为++，–和==（没有=，+，-，*，/，%，<,>等任何其他运算符），也没有循环及goto语句，除此之外与C相同。使用C–编写一个函数int
mod(int a,int b)，计算a除以b的余数。

——来自wweiyi暑假集训

题意简述：只用++,–,==运算符和C++的其他功能来完成a%b的功能

提示：允许调用其他函数

这是一道神奇的题目，我想了大半天才想出来，甚至引来了老师的批评，接下来我说一说我的思路

这道题我们需要只用++,–,==和C++的其他功能来实现模运算，这个看起开似乎无法实现，因为不能够使用循环，因此，这道题的阴影加深了。

递归！循环的后裔！

这里我们不能用循环，也就是我们需要使用类似循环的一个过程，递归来解决问题，递归是一种很常用的解决问题的方法，将一个大问题转换成一个子问题也许模运算就可以这样解决了。

++，–，==三运算符！三符成虎！

我们要解决模运算首先要解决减法运算的问题，因为a%b，就是a一直减b，减到a小于b为止，因此，我们可以先解决减法运算。

代码如下

1
2
3
4
5
6
int jian(int a,int b)
{
    if(b==0)
        return a;
    return jian(--a,--b);
}

这样就解决了减法运算；

但是顺便说一句，加法和乘法运算实际上也很简单，让我来把代码贴出来！

1
2
3
4
5
6
7
8
9
10
11
12
int add(int a,int b)
{
    if(b==0)
        return a;
    return add(++a,--b);
}
int cheng(int a,int b)
{
    if(b==0)
        return a;
    return add(a,cheng(a,--b));
}

我们可以轻松地解决减法，乘法和加法，但是模运算我们还是不知道，怎么办呢？

判断！事情的转机？

我们再次理清一下思路，我们需要a一直减b，一直减到a小于b为止，也就是mod(a,b)=mod(a-b,b)，这就是神奇的递归式，就可以解决一部分问题，另一部分问题就是判断a小于b，我们可以a，b同时递减，看谁先到0，但由于这个问题的特殊性，当a=b时，需要特殊判断一下，因为一个数mod它的因数等于0，所以我们的思路就出来了，代码也就写出来了。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
using namespace std;
int pd(int a,int b)
{
	if(a==b)
	return 0;
	if(a==0)
	return 1;
	if(b==0)
	return 0;
	return pd(--a,--b);
}
int jian(int a,int b)
{
	if(b==0)
	return a;
	return jian(--a,--b);
}
int mod(int a,int b)
{
	if(pd(a,b)==1)
	return a;
	return mod(jian(a,b),b);
}
int main()
{
	int a,b;
	cin>>a>>b;
	cout<<mod(a,b)<<endl;
	return 0;
}
//wweiyi费时3小时智造