暴力：竖式问题

雨点打透心脏的1/2处 2023-10-06 16:55 44阅读 0赞

## 暴力：竖式问题 ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]

#### 思路：暴力枚举（将构造性问题转化为验证性问题） ####

我们可以遍历数字集合，去选取满足条件的竖式，但这种方法十分麻烦，因为我们需要找出5个数字，将会有5个for循环，所以这种方法肯定是不可取的

我们可以换一种思路，既然从数字集合中构造竖式十分困难，但是三位数总共就是100~999，两位数总共是10 ~ 99，我们可以遍历所有的三位数和两位数，再去验证它们是否满足条件，这样我们就将构造性问题转换为了验证性问题。

我们用一个标记数组记录数字集合中出现的数字，数组大小可设为11，因为总共就只有0 ~9这几个数字。我们还需写一个判断数字是否满足条件的函数，只需将数字不断对10取余，判断余数是否在集合内，然后将其除以10，依次类推即可。

需注意的几点：

*  不能用c语言的scanf扫描string对象，string是C++特有的，scanf无法扫描，由于数字集合最多把0~9全部包含，我们先设一个字符数组char s\[15\]即可，然后用scanf( “%s”,s )来扫描输入
 *  可用memset( table,0,sizeof( table ) )来将标记数组初始化
 *  可用strlen(s)返回s的长度
 *  如何输出<1>?使用printf( “<%d>\\n”,++clock )即可
 *  如何输出竖式？输出方式为“%5d”表示按5位的固定位宽输出整型数值。如果不足5位，则在前面补空格；超过5位，则按实际位数输出。 输出竖式用`printf( "%5d\nX%4d\n-----\n%5d\n%4d\n-----\n%5d\n\n",i,j,temp1,temp2,i*j );`即可

#### 代码： ####

# include <bits/stdc++.h>
    using namespace std;
    bool judge( int num,int* table )
    {
        
    	while( num!=0 )
    	{
        
    		if( table[ num%10 ]==0 )
    			return false;
    		num=num/10; 
    	}
    	return true;
    }
    int main()
    {
        
    	char s[15];
    	int table[11];
    	int i;
    	int j;
    	int clock;
    	while( scanf( "%s",s )!=EOF )
    	{
        	
    		clock=0;
    		memset( table,0,sizeof( table ) );
    		for( i=0;i<strlen( s );i++ )
    		{
        
    			table[ s[i]-'0' ]=1;
    		}
    		for( i=100;i<=999;i++ )
    		{
        
    			if( judge( i,table )==false )
    				continue;
    			for( j=10;j<=99;j++ )
    			{
        
    				if( judge( j,table )==false )
    					continue;
    				int temp1=i*( j%10 );
    				int temp2=i*( j/10 );
    				if( judge( temp1,table )==false || judge( temp2,table )==false )
    					continue;
    				if( judge( i*j,table )==false )
    					continue;
    				printf( "<%d>\n",++clock );
    				printf( "%5d\nX%4d\n-----\n%5d\n%4d\n-----\n%5d\n\n",
    						i,j,temp1,temp2,i*j );
    			}
    		}
    		printf( "The number of solutions: %d\n",clock );
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210320093054819.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210320093108631.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70