【蓝桥杯】【啊哈！算法】深度优先搜索——坑爹的奥数

分手后的思念是犯贱 2022-11-17 14:57 282阅读 0赞

## [【啊哈！算法】系列文章目录][Link 1] ##

--------------------

### 目录 ###

*   *  【啊哈！算法】系列文章目录
     *   *  需求介绍
         *  解答

--------------------

### 需求介绍 ###

口口口＋口口口＝口口口，将数字1~9分别填入9个口中， 每个数字只能使用一次使得等式成立。例如173+286=459就是一个合理的组合， 请问一共有多少种合理的组合呢？ **注意：** 173+286=459 与 286+173 =459 是同一种组合！

### 解答 ###

#include <iostream>
    #include <ctime>
    using namespace std;
    
    #define N 9
    int map[N] = { 1,2,3,4,5,6,7,8,9};
    int a[N];
    int book[N] = { 0};
    int count=0;
    
    //暴力dfs查找 
    void dfs1(int step)
    { 
    	if(step==N)
    	{ 
    		if(a[0]*100+a[1]*10+a[2] + a[3]*100+a[4]*10+a[5] == a[6]*100+a[7]*10+a[8])
    		{ 
    			count++;
    		}
    		return;
    	}
    	
    	for(char i=0; i<N; i++)
    	{ 
    		if(book[i]==0)
    		{ 
    			a[step] = map[i];
    			book[i] = 1;
    			
    			dfs1(step+1);
    			
    			book[i] = 0;
    		}
    	}
    }
    
    //优化1：前两个数的和不可能大于1000 
    void dfs2(int step)
    { 
    	if(step==6)
    	{ 
    		if(a[0]*100+a[1]*10+a[2] + a[3]*100+a[4]*10+a[5] >= 1000)
    		{ 
    			return;
    		}
    	}
    	
    	if(step==N)
    	{ 
    		if(a[0]*100+a[1]*10+a[2] + a[3]*100+a[4]*10+a[5] == a[6]*100+a[7]*10+a[8])
    		{ 
    			count++;
    		}
    		return;
    	}
    	
    	for(char i=0; i<N; i++)
    	{ 
    		if(book[i]==0)
    		{ 
    			a[step] = map[i];
    			book[i] = 1;
    			
    			dfs2(step+1);
    			
    			book[i] = 0;
    		}
    	}
    	
    }
    
    int max_element_f(void)
    { 
    	int max=0;
    	for(char i=0; i<N; i++)
    	{ 
    		if(book[i]==0 && map[i]>max)
    		{ 
    			max	= map[i];
    		}
    	}
    	return max;
    } 
    
    //优化2：排除 剩余的三个数字中的最大的数小于前两个数的和的百位 
    void dfs3(int step)
    { 
    	if(step==6)
    	{ 
    		int sum = a[0]*100+a[1]*10+a[2] + a[3]*100+a[4]*10+a[5];
    		if(sum >= 1000)
    		{ 
    			return;
    		}
    		
    		if(sum/100 > max_element_f())
    		{ 
    			return;
    		}
    	}
    	
    	if(step==N)
    	{ 
    		if(a[0]*100+a[1]*10+a[2] + a[3]*100+a[4]*10+a[5] == a[6]*100+a[7]*10+a[8])
    		{ 
    			count++;
    		}
    		return;
    	}
    	
    	for(char i=0; i<N; i++)
    	{ 
    		if(book[i]==0)
    		{ 
    			a[step] = map[i];
    			book[i] = 1;
    			
    			dfs3(step+1);
    			
    			book[i] = 0;
    		}
    	}
    	
    }
    
    //优化3：分别查看剩余的三个数字 是否与sum个十百位中的其中一个相等 
    void dfs4(int step)
    { 
    	if(step==6)
    	{ 
    		int sum = a[0]*100+a[1]*10+a[2] + a[3]*100+a[4]*10+a[5];
    		if(sum >= 1000)
    		{ 
    			return;
    		}
    		
    		int bai = sum/100;
    		int shi = sum/10%10;
    		int ge  = sum%10;
    		for(char i=0; i<N; i++)
    		{ 
    			if(book[i]==0)
    			{ 
    				if(!(map[i]==ge||map[i]==shi||map[i]==bai))	return;
    			}
    		}
    	}
    	
    	if(step==N)
    	{ 
    		if(a[0]*100+a[1]*10+a[2] + a[3]*100+a[4]*10+a[5] == a[6]*100+a[7]*10+a[8])
    		{ 
    			count++;
    		}
    		return;
    	}
    	
    	for(char i=0; i<N; i++)
    	{ 
    		if(book[i]==0)
    		{ 
    			a[step] = map[i];
    			book[i] = 1;
    			
    			dfs4(step+1);
    			
    			book[i] = 0;
    		}
    	}
    }
    
    //带输出的dfs 
    void dfs0(int step)
    { 
    	if(step==6)
    	{ 
    		int sum = a[0]*100+a[1]*10+a[2] + a[3]*100+a[4]*10+a[5];
    		
    		if(sum >= 1000)
    		{ 
    			return;
    		}
    		
    		int bai = sum/100;
    		int shi = sum/10%10;
    		int ge  = sum%10;
    		for(char i=0; i<N; i++)
    		{ 
    			if(book[i]==0)
    			{ 
    				if(!(map[i]==ge||map[i]==shi||map[i]==bai))	return;
    			}
    		}
    	}
    	
    	if(step==N)
    	{ 
    		if(a[0]*100+a[1]*10+a[2] + a[3]*100+a[4]*10+a[5] == a[6]*100+a[7]*10+a[8])
    		{ 	
    			cout << a[0] << a[1] << a[2] << " + " << a[3] << a[4] << a[5] << \
    			" = " << a[6] << a[7] << a[8] << endl;
    		}
    		return;
    	}
    	
    	for(char i=0; i<N; i++)
    	{ 
    		if(book[i]==0)
    		{ 
    			a[step] = map[i];
    			book[i] = 1;
    			
    			dfs0(step+1);
    			
    			book[i] = 0;
    		}
    	}
    	
    }
    
    int main()
    { 
    	clock_t start, end;
    	int clock_num=10;
    	
    	count = 0;
    	start = clock();
    	for(char i=0; i<clock_num; i++)dfs1(0);
    	end = clock();
    	cout << "dfs1: ";
    	cout << (end-start) << endl;
    	
    	//优化1：前两个数的和不可能大于1000 
    	count = 0;
    	start = clock();
    	for(char i=0; i<clock_num; i++)dfs2(0);
    	end = clock();
    	cout << "dfs2: ";
    	cout << (end-start) << endl;
    	
    	//优化2：排除 剩余的三个数字中的最大的数小于前两个数的和的百位 
    	count = 0;
    	start = clock();
    	for(char i=0; i<clock_num; i++)dfs3(0);
    	end = clock();
    	cout << "dfs3: ";
    	cout << (end-start) << endl;
    	
    	//优化3：分别查看剩余的三个数字 是否与sum个十百位中的其中一个相等 
    	count = 0;
    	start = clock();
    	for(char i=0; i<clock_num; i++)dfs4(0);
    	end = clock();
    	cout << "dfs4: ";
    	cout << (end-start) << endl;
    
    	
    	cout << "共有" << count/2/clock_num << "种组合，分别为"; 
    	cout << "（此处输出" << count/clock_num << "种，包括重复的）:" << endl;
    	dfs0(0);
    
    	return 0;
    }

--------------------

输出为：

dfs1: 245
    dfs2: 96
    dfs3: 79
    dfs4: 24
    共有168种组合，分别为（此处输出336种，包括重复的）:
    124 + 659 = 783
    125 + 739 = 864
    127 + 359 = 486
    127 + 368 = 495
    128 + 367 = 495
    128 + 439 = 567
    129 + 357 = 486
    129 + 438 = 567
    129 + 654 = 783
    129 + 735 = 864
    134 + 658 = 792
    135 + 729 = 864
    138 + 429 = 567
    138 + 654 = 792
    139 + 428 = 567
    139 + 725 = 864
    142 + 596 = 738
    142 + 695 = 837
    143 + 586 = 729
    145 + 692 = 837
    146 + 583 = 729
    146 + 592 = 738
    152 + 487 = 639
    152 + 784 = 936
    154 + 629 = 783
    154 + 638 = 792
    154 + 782 = 936
    157 + 329 = 486
    157 + 482 = 639
    158 + 634 = 792
    159 + 327 = 486
    159 + 624 = 783
    162 + 387 = 549
    162 + 783 = 945
    163 + 782 = 945
    167 + 328 = 495
    167 + 382 = 549
    168 + 327 = 495
    173 + 286 = 459
    173 + 295 = 468
    175 + 293 = 468
    176 + 283 = 459
    182 + 367 = 549
    182 + 394 = 576
    182 + 457 = 639
    182 + 493 = 675
    182 + 754 = 936
    182 + 763 = 945
    183 + 276 = 459
    183 + 492 = 675
    183 + 546 = 729
    183 + 762 = 945
    184 + 392 = 576
    184 + 752 = 936
    186 + 273 = 459
    186 + 543 = 729
    187 + 362 = 549
    187 + 452 = 639
    192 + 384 = 576
    192 + 483 = 675
    192 + 546 = 738
    192 + 645 = 837
    193 + 275 = 468
    193 + 482 = 675
    194 + 382 = 576
    195 + 273 = 468
    195 + 642 = 837
    196 + 542 = 738
    214 + 569 = 783
    214 + 659 = 873
    215 + 478 = 693
    215 + 748 = 963
    216 + 378 = 594
    216 + 738 = 954
    218 + 349 = 567
    218 + 376 = 594
    218 + 439 = 657
    218 + 475 = 693
    218 + 736 = 954
    218 + 745 = 963
    219 + 348 = 567
    219 + 438 = 657
    219 + 564 = 783
    219 + 654 = 873
    234 + 657 = 891
    235 + 746 = 981
    236 + 718 = 954
    236 + 745 = 981
    237 + 654 = 891
    238 + 419 = 657
    238 + 716 = 954
    239 + 418 = 657
    241 + 596 = 837
    243 + 576 = 819
    243 + 675 = 918
    245 + 673 = 918
    245 + 718 = 963
    245 + 736 = 981
    246 + 573 = 819
    246 + 591 = 837
    246 + 735 = 981
    248 + 319 = 567
    248 + 715 = 963
    249 + 318 = 567
    251 + 397 = 648
    254 + 619 = 873
    254 + 637 = 891
    257 + 391 = 648
    257 + 634 = 891
    259 + 614 = 873
    264 + 519 = 783
    269 + 514 = 783
    271 + 593 = 864
    271 + 683 = 954
    273 + 186 = 459
    273 + 195 = 468
    273 + 546 = 819
    273 + 591 = 864
    273 + 645 = 918
    273 + 681 = 954
    275 + 193 = 468
    275 + 418 = 693
    275 + 643 = 918
    276 + 183 = 459
    276 + 318 = 594
    276 + 543 = 819
    278 + 316 = 594
    278 + 415 = 693
    281 + 394 = 675
    281 + 673 = 954
    283 + 176 = 459
    283 + 671 = 954
    284 + 391 = 675
    286 + 173 = 459
    291 + 357 = 648
    291 + 384 = 675
    291 + 546 = 837
    291 + 573 = 864
    293 + 175 = 468
    293 + 571 = 864
    294 + 381 = 675
    295 + 173 = 468
    296 + 541 = 837
    297 + 351 = 648
    314 + 658 = 972
    316 + 278 = 594
    317 + 529 = 846
    317 + 628 = 945
    318 + 249 = 567
    318 + 276 = 594
    318 + 627 = 945
    318 + 654 = 972
    319 + 248 = 567
    319 + 527 = 846
    324 + 567 = 891
    324 + 657 = 981
    327 + 159 = 486
    327 + 168 = 495
    327 + 519 = 846
    327 + 564 = 891
    327 + 618 = 945
    327 + 654 = 981
    328 + 167 = 495
    328 + 617 = 945
    329 + 157 = 486
    329 + 517 = 846
    341 + 586 = 927
    342 + 576 = 918
    346 + 572 = 918
    346 + 581 = 927
    348 + 219 = 567
    349 + 218 = 567
    351 + 297 = 648
    352 + 467 = 819
    354 + 618 = 972
    354 + 627 = 981
    357 + 129 = 486
    357 + 291 = 648
    357 + 462 = 819
    357 + 624 = 981
    358 + 614 = 972
    359 + 127 = 486
    362 + 187 = 549
    362 + 457 = 819
    364 + 527 = 891
    367 + 128 = 495
    367 + 182 = 549
    367 + 452 = 819
    367 + 524 = 891
    368 + 127 = 495
    372 + 546 = 918
    376 + 218 = 594
    376 + 542 = 918
    378 + 216 = 594
    381 + 294 = 675
    381 + 546 = 927
    382 + 167 = 549
    382 + 194 = 576
    384 + 192 = 576
    384 + 291 = 675
    386 + 541 = 927
    387 + 162 = 549
    391 + 257 = 648
    391 + 284 = 675
    392 + 184 = 576
    394 + 182 = 576
    394 + 281 = 675
    397 + 251 = 648
    415 + 278 = 693
    418 + 239 = 657
    418 + 275 = 693
    419 + 238 = 657
    428 + 139 = 567
    429 + 138 = 567
    438 + 129 = 567
    438 + 219 = 657
    439 + 128 = 567
    439 + 218 = 657
    452 + 187 = 639
    452 + 367 = 819
    457 + 182 = 639
    457 + 362 = 819
    462 + 357 = 819
    467 + 352 = 819
    475 + 218 = 693
    478 + 215 = 693
    482 + 157 = 639
    482 + 193 = 675
    483 + 192 = 675
    487 + 152 = 639
    492 + 183 = 675
    493 + 182 = 675
    514 + 269 = 783
    517 + 329 = 846
    519 + 264 = 783
    519 + 327 = 846
    524 + 367 = 891
    527 + 319 = 846
    527 + 364 = 891
    529 + 317 = 846
    541 + 296 = 837
    541 + 386 = 927
    542 + 196 = 738
    542 + 376 = 918
    543 + 186 = 729
    543 + 276 = 819
    546 + 183 = 729
    546 + 192 = 738
    546 + 273 = 819
    546 + 291 = 837
    546 + 372 = 918
    546 + 381 = 927
    564 + 219 = 783
    564 + 327 = 891
    567 + 324 = 891
    569 + 214 = 783
    571 + 293 = 864
    572 + 346 = 918
    573 + 246 = 819
    573 + 291 = 864
    576 + 243 = 819
    576 + 342 = 918
    581 + 346 = 927
    583 + 146 = 729
    586 + 143 = 729
    586 + 341 = 927
    591 + 246 = 837
    591 + 273 = 864
    592 + 146 = 738
    593 + 271 = 864
    596 + 142 = 738
    596 + 241 = 837
    614 + 259 = 873
    614 + 358 = 972
    617 + 328 = 945
    618 + 327 = 945
    618 + 354 = 972
    619 + 254 = 873
    624 + 159 = 783
    624 + 357 = 981
    627 + 318 = 945
    627 + 354 = 981
    628 + 317 = 945
    629 + 154 = 783
    634 + 158 = 792
    634 + 257 = 891
    637 + 254 = 891
    638 + 154 = 792
    642 + 195 = 837
    643 + 275 = 918
    645 + 192 = 837
    645 + 273 = 918
    654 + 129 = 783
    654 + 138 = 792
    654 + 219 = 873
    654 + 237 = 891
    654 + 318 = 972
    654 + 327 = 981
    657 + 234 = 891
    657 + 324 = 981
    658 + 134 = 792
    658 + 314 = 972
    659 + 124 = 783
    659 + 214 = 873
    671 + 283 = 954
    673 + 245 = 918
    673 + 281 = 954
    675 + 243 = 918
    681 + 273 = 954
    683 + 271 = 954
    692 + 145 = 837
    695 + 142 = 837
    715 + 248 = 963
    716 + 238 = 954
    718 + 236 = 954
    718 + 245 = 963
    725 + 139 = 864
    729 + 135 = 864
    735 + 129 = 864
    735 + 246 = 981
    736 + 218 = 954
    736 + 245 = 981
    738 + 216 = 954
    739 + 125 = 864
    745 + 218 = 963
    745 + 236 = 981
    746 + 235 = 981
    748 + 215 = 963
    752 + 184 = 936
    754 + 182 = 936
    762 + 183 = 945
    763 + 182 = 945
    782 + 154 = 936
    782 + 163 = 945
    783 + 162 = 945
    784 + 152 = 936

[Link 1]: https://blog.csdn.net/weixin_43964993/article/details/115446128