冒泡排序的應用——6174問題

冒泡排序的應用——6174問題

• 問題叙述：

       輸入一個n位數，把所有數字從大到小排序後得到a,從小到大排序得到b,用a-b替換原來的數，并繼續操作，直到出現循環，即新得到的數曾經得到過。如：初始為1234，依次可得4321-1234=3087、8730-378=8352、8352-2358=6174、而7641-1267=6174，即回到本身。

• 問題分析及解決：

       不難看出，我們需要解決兩個問題，如何得到下一個數？如何判斷這個數是否出現過？需要得到下一個數，就要解決各個數字排序問題，這也是我們今天重點應用的排序算法——冒泡排序。代碼如下：

int get_number(int x)
{
	int a, b, n;
	char p[10];
	//轉化成字元串
	sprintf(p, "%d", x);
	n = strlen(p);    
	//冒泡排序
	for(int i = 0; i < n; i++)
		for(int j = i+1; j < n;j++)
			if (p[i] > p[j])
			{
				char t = p[i];
				p[i] = p[j];
				p[j] = t;
			}
	sscanf(p, "%d", &b);
	//反轉即倒序輸出
	for (int i = 0; i < n / 2; i++)
	{
		char t = p[i];
		p[i] = p[n-1-i];
		p[n-1-i] = t;

	}
	sscanf(p, "%d", &a);
	return a - b;
}
           

逐一生成各個數，并判斷是否生成過，這裡我們使用最常用的數組進行存儲，代碼如下：

int num[2000], count;
int main()
{
	scanf("d", &num[0]);
	printf("d", num[0]);
	count = 1;
	for (;;)
	{
		//生成并輸出下一個數
		num[count] = get_number(num[count - 1]);
		printf("->%d", num[count]);
		//在數組中尋找新生成的數
		int found = 0;
		for(int i = 0; i< count; i++)
		{
			if (num[i] == num[count])
			{
				found = 1;
				break;
			}
		}
		//若找到，退出循環
		if (found)
			break;
		count++;
	}
	printf("\n");
	return 0;
}

           

冒泡排序一直由于其簡潔的思想方法而倍受青睐，但也有其不足，這就需要我們對算法進行優化，以後會更新的哦&&&