/*************************************************************************
	>?File?Name:?Kproduct.cpp
	>?Author:?wuchenyang
	>?Created?Time:?2015年05月10日?星期六?19時14分18秒

	算法思路：
	
	采用動態規劃法求解：
	n為數字長度，k為劃分個數;
	p[i][k]?表示0～i?所表示數字的十進制數?最大k乘積，?c[k+1][i]表示數字?n-i+1～i?所表示的十進制數
	1.若k值為1則0～n所表示的十進制數為最大;
	2.若k>0?&&?k
?************************************************************************/

#include
#include
#include
#include
#include
using?namespace?std;

class?product
{	int?n;
	int?k;
	int?c[10][10];
	int?p[10][5];
	int?num[10];
	string?data;
	int?pmax;

	public?:
	void?readfile（）;
	void?init_Arryc（）;
	void?charToInt（）;
	void?productArry（）;
	void?writeTofile（）;
};

/*寫入文件*/
void?product::writeTofile（）
{
	ofstream?outf（“/home/xiaoquan/suanfa/output.txt“）;
	if（!outf.is_open（））
	{
		cout<<“open?the?file?failed!“<	}
	outf<	outf.close（）;
}

/*最大k乘積*/
void?product::productArry（）
{
	p[n][k];
	
	if（n<0|k>n-1|k<0）????/*k?或者?n?的值不合法*/
	{
		cout<<“k?value?or?n?value?is?not?right!“<	}
	if（k?==?1）??????/*k值為1*/
		{
			cout<<“最大k乘積為：“<		}
	else?
	{
		for（int?i?=?1;?i		{
			p[i][1]?=?c[1][i];
		}
		for（int?i?=?1;?i<=?n;i++）
		{
			for（int?j?=?2;?j<=k?;j++）
			{
	
	
				int?max?=?0;
				for（int?k?=?1;k				{
		i			int?temp?=?p[k][j-1]?*?c[k+1][i];
				
					if（temp?>?max）
					{
						max?=?temp;
					}
				}
				p[i][j]?=?max;
			}
		}
	
	pmax?=?p[n][k];
	cout<<“數組p:“<	for（int?i?=?1;?i<=?n;i++）
	{
		for（int?j?=?1;j<=?n;j++）
		{
			cout<		
		}
		cout<	}
	cout<<“最大k乘積為：“<	}
}

/*初始化數組*/
void?product::init_Arryc（）
{
	?c[n][n];
	cout<<“c:“<	for（int?i?=?1;?i?<=?n;?i++）
	{
		c[i][i]?=?num[i];
		for（int?j?=?i+1;?j?<=?n;?j++）
		{
			c[i][j]?=?c[i][j-1]*10?+?num[j];
//			cout<		}
		cout<
	}
	for（int?i?=?1;?i<=n;?i++）
	{
		for（int?j?=?1;?j<=n;?j++）
		{
			cout<		}
		cout<	}
}

/*將字符數組轉化為整型數組*/
void?product::charToInt（）
{
	num[n]?=?0;
	cout<<“data:“<	cout<<“num:“<	for（int?i?=?0?;i?	{
		num[i+1]?=?data[i]?-?‘0‘;
		cout<	}
}

/*讀取文件*/
void?product::readfile（）
{
	char?line1[20];
	char?line2[20];

	string?x1x2;
//	int?nk;

	ifstream?inf（“/home/xiaoquan/suanfa/input.txt“）;
	if（!inf.is_open（））
	{
		cout<<“open?file?error!“<	}

	inf.getline（line1sizeof（line1））;
	inf.getline（line2sizeof（line2））;	
//	cout<	stringstream?word（line1）;//提取空格讀取文件第一行
	word>>x1;
	word>>x2;
	
	n?=?atoi（x1.c_str（））;???//將字符串類型轉化為整型
	k?=?atoi（x2.c_str（））;
	
	data?=?line2;
//	cout<<“n=?“<//	cout<<“x1=“<

}

int?main（）
{
	product?pc?;
	pc.readfile（）;
????pc.charToInt（）;
	pc.init_Arryc（）;
	pc.productArry（）;
	pc.writeTofile（）;
	return?0;
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件????????3200??2015-05-12?17:57??最大k乘積\Kproduct.cpp
?????文件?????????304??2015-05-16?09:22??最大k乘積\readme.txt
?????目錄???????????0??2015-05-16?09:07??最大k乘積\