encode.cpp

有m￥n(m￡100,n￡100)个金币在桌面上排成一个m行n列的金币阵列。每一枚金 币或正面朝上或背面朝上。用数字表示金币状态

#include <iostream>
#include<fstream>
#include<iostream>
#include <time.h>

using namespace std;

long Dictionary(char s[]);

int main()
{
    time_t startTime;
    time_t endTime;
	
	ifstream input("input.txt");
		ofstream output("output.txt");
	
		int n,m;
		char s[27]={0x00};
		input>>n;
		for(int i=0;i<=n;i++)
		{
			input.getline(s,27);
			if(i!=0)
			{
				output<<Dictionary(s)<<'\n';
			}		
		}
	
    
    cout << s << " : " << Dictionary(s) << endl;
    
    time(&endTime);
    cout << "time = " << difftime(endTime, startTime) << endl;
    system("pause");
    return 0;
}

int Gcd(int m, int n)//求最大公约数 
{
    int temp;
    
    while (n > 0)
    {
        temp = m % n;
        m = n;
        n = temp;
    }
    return m;
}


long Combination(int m, int n)//求组合C(m, n)，注意不能直接按定义求，否则会溢出，先约分再除 
{    
    int *pm = new int[m];
    int *pn = new int[m];
    
    for (int i=0; i<m; ++i)
        pm[i] = i + 1;
    for (i=0; i<m; ++i)
        pn[i] = n - i;
    
    int g;
    for (i=0; i<m; ++i)
        for (int j=0; j<m; ++j)
        {
            g = Gcd(pm[i], pn[j]);//求最大公约数 
            pm[i] /= g;
            pn[j] /= g;
        }
        
		long numerator = 1;
		long denominator = 1;
		
		for (i=0; i<m; ++i)
			numerator *= pn[i];
		for (i=0; i<m; ++i)
			denominator *= pm[i];
        
		return numerator / denominator;
}

long Dictionary(char s[])
{
    long sum = 0;
    int len = strlen(s);
    int a[27] = {0};
    
    for (int i=0; i<len; ++i)//记录出现的字母，相应的元素值为1，为出现的字母对应元素值为0 
        a[s[i]-'a'+1] = 1;
    for (i=1; i<27; ++i)
        cout << a[i] << " "; cout << endl << endl;
    
	
    for (i=0; i<len-1; ++i)//先计算长度小于len的字符串的编码 
        sum += Combination(i+1, 26);
    cout << "sum = " << sum << endl;
    
    i = 1;
    for (; i<26 && len>1; ++i)//分析字符串，直到长度len为1 
    {
        if (a[i] == 0)//如果该字母未出现，计算以他开头的字符串个数 
            sum += Combination(len-1, 26-i);
        else //否则消去该字母，即字符串长度减1 
            --len;
    }
    while (a[i++] == 0)//计算最后一个字母的位置 
        ++sum;
	
    return sum + 1;//返回编码值 
}