《编程思维与实践》1072.下一位妙数

题目

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iP2g5mGu-1684045940889)(C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20230514140312682.png)]$

思路

思路与最小不重复数基本一致,从最高位开始找到第一个出现9的位置,让其加1,后面全变为0即可.

只需要再加一个判定条件:不能被9整除.

由数学知识,一个数不能被9整除当且仅当各位数之和不能被9整除.

这里给出简单的证明:
$不妨以三位数abc为例,abc=a\cdot100+b\cdot10+c\\ \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\,\,\,\,=(a+b+c)+(99a+9b)\\ 由\,\,9|99a+9b\,知\,\,9|abc\,\,当且仅当\,\,9|a+b+c$
类似地,一个数不能被3整除当且仅当各位数之和不能被3整除.

代码

#include<stdio.h>
#include<string.h>
#define N 101

typedef struct{int cnt,v[N];}BIGINT;

BIGINT carry(BIGINT S,int n);   //进位 n表示进制 
BIGINT add1(BIGINT S,int pos);  
int judge1(BIGINT S);  //判断是否整除 不能整除返回-1
int judge2(BIGINT S);  //判断是否出现9 返回9的位置 不出现返回-1

int main()
{
	char s[N+1];
	scanf("%s",s);
    BIGINT A={strlen(s),{0}};
    for(int i=0;i<strlen(s);i++)
	{
		A.v[A.cnt-1-i]=s[i]-'0';  //逆向存
	}
	A=add1(A,0);  //先最后一位加1
	while(!(judge1(A)==-1&&judge2(A)==-1))  //循环条件:能被9整除或者出现9
	{
        if(judge2(A)!=-1) //出现9
        {
            int temp=judge2(A);
            A=add1(A,temp);
            for(int i=temp-1;i>=0;i--)  //后面全赋为0
            {
                A.v[i]=0;
            }
        }
        else  //没出现9 但能被9整除
        {
            A=add1(A,0);  //最后一位加1
        }
	}
	for(int i=A.cnt-1;i>=0;i--)
   	{
    	printf("%d",A.v[i]);
    }
    printf("\n");
    return 0;
}

int judge1(BIGINT S)  //判断是否整除
{
	int count=0;
	for(int i=0;i<S.cnt;i++)
	{
		count+=S.v[i];
	}
	if(count%9==0)
	{
		return 1;  //能被9整除
	}
	else
    {
		return -1;  //不能被9整除
	}
}

int judge2(BIGINT S)  //判断是否出现9 返回9的位置
{
	for(int i=S.cnt-1;i>=0;i--)
	{
		if(S.v[i]==9)
		{
			return i;
		}
	}
	return -1;
}

BIGINT carry(BIGINT S,int n)   //进位 n表示进制 
{
	int flag=0;
	for(int i=0;i<S.cnt;i++)
	{
		int temp=S.v[i]+flag;
		S.v[i]=temp%n;
		flag=temp/n;
	}
    if(flag)   //为了加法进行的方便 可能多一位
    {
        S.v[S.cnt++]=flag;
    }
	return S;
}

BIGINT add1(BIGINT S,int pos)     //两个大整数相加
{
	S.v[pos]+=1;
	S=carry(S,10);
	return S;
}
``