/*
  Name: 
  Copyright: 
  Author: 
  Date: 03-05-07 22:25
  Description: ===================================================================
算法实现题1-2 字典序问题

问题描述：

在数据加密和数据压缩中常需要对特殊的字符串进行编码。给定的字母表A 由26 个小
写英文字母组成A={a,b,…,z}。该字母表产生的升序字符串是指字符串中字母按照从左到右出现的次序与字母在字母表中出现的次序相同，且每个字符最多出现1 次。例如，
a,b,ab,bc,xyz 等字符串都是升序字符串。现在对字母表A 产生的所有长度不超过6 的升序字符串按照字典序排列并编码如下。
1 2 … 26 27 28 …
a b … z ab ac …
对于任意长度不超过6 的升序字符串，迅速计算出它在上述字典中的编码。

编程任务：

对于给定的长度不超过6 的升序字符串，编程计算出它在上述字典中的编码。

数据输入：

输入数据由文件名为input.txt的文本文件提供。
文件的第一行是一个正整数k，表示接下来共有k 行。
接下来的k行中，每行给出一个字符串。

结果输出:

程序运行结束时，将计算结果输出到文件output.txt 中。文件共有k 行，每行对应于一
个字符串的编码。
输入文件示例 输出文件示例
input.txt 
2
a
b

output.txt
1
2
====================================================================
*/

/*
算法思路：设置一个长为27的数组a，从下标1开始，分别表示26个字母，赋初值为0。
记录被测试的字符串的长度len，在数组a记录出现的字符----将所对应的元素赋值为1。
很明显，当len = 1时，返回的编码就是数组中值为1的下标；当len = 2时，应该先把len = 1时的所有可能情况加起来（即从26个字母中取1个，也即组合数Combination(1, 26)），再去分析具体的字符串。
当len = 3时，应该先把len = 1和2时的所有可能情况加起来（即从26个字母中取1个和2个，也即组合数Combination(1, 26)）和Combination(2, 26)），再去分析具体的字符串。
依次类推，当len = i时，应该先把len = 1，2，。。。i-1时的所有可能情况加起来，再去分析具体的字符串。 
那么如何分析具体的字符串呢？以"cdf"为例，它对应的数组a[27] = {0，0，0，1，1，0，1，0，0，。。。0}。
因为a[1] = 0，说明字母a没有出现，而"cdf"肯定排在以a开头的长度为3的字符串的后面，以a开头的长度为3的字符串的个数为Combination(3-1, 26-1)，即从25个字母中取2个）；
同样"cdf"肯定排在以b开头的长度为3的字符串的后面，所以编码还要加上Combination(3-1, 26-2)；
3号元素‘c’为1，跳过，长度减1；接着跳过4号元素，长度再减1，此时长度已经是1了，只要看最后一个字符和倒数第2个字符相差几就行了相差几就加几，最后的和即是所要的编码。
一个例子可能不够，再举一个。 
以"begi"为例，它对应的数组a[27] = {0，0，1，0，0，1，0，1，0，1，0，。。。0}。
因为a[1] = 0，说明字母a没有出现，而"begi"肯定排在以a开头的长度为4的字符串的后面，以a开头的长度为4的字符串的个数为Combination(4-1, 26-1)，即从25个字母中取3个）；
2号元素‘b’为1，跳过，长度减1；剩下的字符串为"egi" ； 
3号元素‘c’为0，不能跳过，"egi"肯定排在以c开头的长度为3的字符串的后面，
以c开头的长度为3的字符串的个数为Combination(3-1, 26-3)，即从23个字母中取2个）；
同理4号元素‘d’不能跳过， 编码还要加上Combination(3-1, 26-4)；
5号元素‘e’为1，跳过，长度减1；剩下的字符串为"gi" ； 
同理6号元素‘f’不能跳过， 编码还要加上Combination(2-1, 26-6)；
7号元素‘g’为1，跳过，长度减1；剩下的字符串为"i" ； 
此时长度已经是1了，只要看最后一个字符和倒数第2个字符（即i和g）相差几就行了相差几就加几，最后的和即是所要的编码。

原题字符串的长度不超过6，我这里可以增加到26 
表达能力有限，大家看代码，自己领会。 
*/

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

using namespace std;

long long Dictionary(char s[]);

int main()
{
    time_t startTime;
    time_t endTime;
    
    char s[] = "nopqrstuvw";
    
    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 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 (int i=0; i<m; ++i)
        pn[i] = n - i;
    
    int g;
    for (int 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 long numerator = 1;
    long long denominator = 1;
    
    for (int i=0; i<m; ++i)
        numerator *= pn[i];
    for (int i=0; i<m; ++i)
        denominator *= pm[i];
        
    return numerator / denominator;
}

long long Dictionary(char s[])
{
    long 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 (int i=1; i<27; ++i)
        cout << a[i] << " "; cout << endl << endl;
    

    for (int i=0; i<len-1; ++i)//先计算长度小于len的字符串的编码 
        sum += Combination(i, 26);
    cout << "sum = " << sum << endl;
    
    int 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;//返回编码值 
}

好  多做点

/*
  Name: 
  Copyright: 
  Author: 
  Date: 03-05-07 11:13
  Description:
===========================BEGIN===============================
算法实现题1-3 最多约数问题

问题描述：

正整数x 的约数是能整除x 的正整数。正整数x 的约数个数记为div(x)。例如，1，2，
5，10 都是正整数10 的约数，且div(10)=4。设a 和b 是2 个正整数，a≤b，找出a 和b
之间约数个数最多的数x。
 
编程任务：
对于给定的2 个正整数a≤b，编程计算a 和b 之间约数个数最多的数。
 

数据输入：
输入数据由文件名为input.txt的文本文件提供。文件的第1 行有2 个正整数a和b。

结果输出:
程序运行结束时，若找到的a 和b 之间约数个数最多的数是x，将div(x)输出到文件
output.txt中。

输入文件示例 输出文件示例
input.txt  output.txt
1 36            9

===========================================================

*/
/*
算法思路：先缩小被分析的数的范围，这样可以减少不少工作量。
然后造一个素数表，利用素数表求某个数的约数的个数，注意约数不能重复也不能遗漏--这里很麻烦。
最后比较返回的约数个数，返回最大值。
表达能力有限，大家看代码，自己领会。 
*/
#include<iostream>
#include <time.h>
#include <math.h>

using namespace std;

int Divisors(int a, int b);
int Div(const int lib[], int len, int n);
int Insert(int a[], int n, int x);//折半插入有序数组中
int PrimeLib(int a[], int n); //使用桶式排序的方法求素数表，n不能太大


int main(int argc, char* argv[])
{
    time_t startTime;
    time_t endTime;

    time(&startTime);

//    for (int i=130000; i<139000; i+=100)
        cout << Divisors(131000, 1311500) << endl;

    cout << endl;

    time(&endTime);
    cout << "time = " << difftime(endTime, startTime) << endl;
    system("pause");
    return 0;
}
//---------------------------------------------------------------------------

int Div(const int lib[], int len, int n)//利用素数表求n的约数的个数 
{
    int a[1000];//假设n的约数的个数不超过1000 
    int m = n;
    int t = 0;
    int i = 0;

    while (m > 0 && i < len)
    {
        while (m > 0 && m % lib[i] == 0)
        {
            m /= lib[i];
            t = Insert(a, t, m);//插入约数，若重复则不插入 
            t = Insert(a, t, n/m);//插入约数 
        }
        ++i;
    }

    for (i=1; i<t-2; ++i)
        for (int j=i+1; j<t-1; ++j)
        {
            if (n/a[i] <= a[j])
                break;
            m = a[i] * a[j];
            if (n%m == 0)
            {
                t = Insert(a, t, m);//插入约数     
                t = Insert(a, t, n/m);//插入约数
            }
        }

    return t;
}

int Insert(int a[], int n, int x)//折半插入有序数组中 
{
    if (x < 1)
        return n;

    int low = 0;
    int high = n - 1;
    int mid;

    while (low <= high) //在a[low。。。high]中折半查找有序插入的位置
    {
        mid = (low + high) / 2;
        if (a[mid] == x)//如果是重复的元素，不插入 
            return n;
        else if (a[mid] > x)
            high = mid - 1;
        else
            low = mid + 1;
    } //while
    
    for (int i=n-1; i>high; i--)//元素后移
        a[i+1] = a[i];
    a[high+1] = x; //插入

    return n + 1;
}

int Divisors(int a, int b)
{
    int n = (int)sqrt(b);//能够被b整除的素数最大值不超过n 
    int *prime = new int[n/2]; //素数的个数最多不超过n/2个 
    int numPrime = PrimeLib(prime, n);//使用桶式排序的方法求素数表

    int number = 0;
    int max = 0;
    int num;
    int s, m;
    for (s=b,m=0; s>1; s>>=1) //获取b的二进制数的位数         
        m++;

    s = 1 << m; //s = 2^m
    //缩小被判断的数的范围，这里最小值取max（a，s/2）
    a = (a < s/2) ? (s/2) : a; 
    a = (a%2==0) ? a : (a+1);
    for (int i=a; i<=b; i+=2)
    {
        num = Div(prime, numPrime, i);//求i的约数的个数 
        if (max < num)
        {
            max = num;
            number = i;
        }
    }

    cout << number << " : ";
    
    delete []prime;

    return max;
}

int PrimeLib(int a[], int n) //使用桶式排序的方法求素数表，n不能太大
{
    bool *p = new bool[n+1];
    for (int i=0; i<=n; i++)
        p[i] = true;
            
    int m = n / 2;
    for (int i=2; i<=m; i++)
    {
        if (p[i])//若i为素数，则i的整数倍必为非素数
        {
            for (int j=2*i; j<=n; j+=i)
                p[j] = false;
        }
    }
    
    int top = 0;
    for (int i=2; i<=n; i++)//累积素数
        if (p[i])
            a[top++] = i;
            
    delete []p;

    return top;
}

/*
  Name: 
  Copyright: 
  Author: 
  Date: 05-05-07 20:49
  Description: 
        ===========================================================

 算法实现题1-4 金币阵列问题

问题描述：

有m x n (m<=100, n<=100 ) 个金币在桌面上排成一个m行n 列的金币阵列。每一枚金
币或正面朝上或背面朝上。用数字表示金币状态，0表示金币正面朝上，1 表示背面朝上。
金币阵列游戏的规则是：
（1）每次可将任一行金币翻过来放在原来的位置上；
（2）每次可任选2 列，交换这2 列金币的位置。

编程任务：

给定金币阵列的初始状态和目标状态，编程计算按金币游戏规则，将金币阵列从初始状
态变换到目标状态所需的最少变换次数。

数据输入：

由文件input.txt给出输入数据。文件中有多组数据。文件的第1行有1 个正整数k，表
示有k 组数据。每组数据的第1 行有2 个正整数m 和n。以下的m行是金币阵列的初始状
态，每行有n 个数字表示该行金币的状态，0 表示金币正面朝上，1 表示背面朝上。接着的m行是金币阵列的目标状态。

结果输出:

将计算出的最少变换次数按照输入数据的次序输出到文件output.txt。相应数据无解时
输出-1。
输入文件示例 输出文件示例
input.txt 
2
4 3
1 0 1
0 0 0
1 1 0
1 0 1
1 0 1
1 1 1
0 1 1
1 0 1
4 3
1 0 1
0 0 0
1 0 0
1 1 1
1 1 0
1 1 1
0 1 1
1 0 1

output.txt

2
-1
*/

/*
算法思路：整个就是递归递归再递归。先先判断初始状态bm和目标状态em各行的金币情况是否满足条件，即某行的同种朝向的金币数量是否相同，如果朝上的不同也没关系，只要bm朝下的与em朝上的金币数量相同也行（只要翻转该行就好了），但是如果两者都不满足，那就肯定不行。如果碰到列数为偶数，朝上的和朝下的相等的情况，
那就记录该行，待会递归求解的时候可以考虑翻转和不翻转两种情况。
如果各行的金币都满足条件，那就开始处理每一列了。因为每次可任意交换2列金币的位置，所以要递归分析各列交换与不交换的情况，寻求最佳解。在考虑各列交换与不交换之前，要先考虑各行翻转和不翻转。 
总而言之一句话，回溯，回溯寻求最佳解。 
表达能力有限，大家看代码，自己领会。 
*/
#include<iostream>
#include <time.h>
#include <math.h>

using namespace std;

void PrintMap(const int map[][100], int m, int n);
int YellowBoy(const int beginMap[][100], const int endMap[][100], int m, int n);//主函数 
int ForReverse(int map[][100], const int endMap[][100], const bool flag[], int m, int n, int t);
int Judge(int map[][100], const int endMap[][100], int m, int n, int t) ;
void Reverse(int map[][100], int row, int n);//翻转第row行 
int Count(const int map[][100], int row, int n, int flag);//累积第row行值为flag的元素的数量
bool EqualCel(const int map[][100], const int endMap[][100], int m, int cel);//判断第t列是否相同
void SwapCel(int map[][100], int m, int cel_1, int cel_2);//交换列t和列i 

int main(int argc, char* argv[])
{
    time_t startTime;
    time_t endTime;

    time(&startTime);

    int m = 4;
    int n = 4;
    int beginMap[100][100] = {{1,1,1,1},
                              {1,0,0,1},
                              {1,0,0,0},
                              {0,1,1,0}};
    int endMap[100][100]   = {{0,0,0,0},
                              {1,0,0,1},
                              {0,1,0,0},
                              {0,1,1,0}};;

    cout << endl << "begin:  " << endl;
    PrintMap(beginMap, m, n);
    cout << endl << "end:  " << endl;
    PrintMap(endMap, m, n);

    cout << endl << YellowBoy(beginMap, endMap, m, n) << endl;

    time(&endTime);
    cout << "time = " << difftime(endTime, startTime) << endl;
    system("pause");
    return 0;
}
//---------------------------------------------------------------------------

void PrintMap(const int map[][100], int m, int n)
{
    for (int i=0; i<m; ++i)
    {
        for (int j=0; j<n; ++j)
            cout << map[i][j] << "  ";
        cout << endl;
    }        
}

int YellowBoy(const int beginMap[][100], const int endMap[][100], int m, int n)//主函数 
{
    int map[100][100];//复制原始阵列 
    for (int i=0; i<m; ++i)
        for (int j=0; j<n; ++j)
            map[i][j] = beginMap[i][j];

    bool flag[100] = {0};//判断某行的金币阵翻转前后是否都满足条件，适用于偶数列的情况 
    int sum = 0;    
        
    for (int i=0; i<m; ++i)//先判断各行的金币情况是否满足条件，即某行的同种金币数量相同 
    {
        if (Count(beginMap,i,n,1) != Count(endMap,i,n,1))//如果第i行的背面朝上金币数不同 
        {
            if (Count(beginMap,i,n,0) == Count(endMap,i,n,1))//若bm朝下的与em朝上的金币数量相同  
            {
                Reverse(map, i, n);//翻转map的第i行 
                ++sum;//累计操作的次数 
            }
            else//否则无解 
                return -1;
        }
        else if (n%2 == 0 && Count(beginMap,i,n,0) == Count(endMap,i,n,1))//翻转前后都满足条件
            flag[i] = true;
    }

    int count = ForReverse(map, endMap, flag, m, n, 0);//递归执行或不执行翻转操作，寻求最佳解 
    if (count == -1)
        return -1;
    return sum + count;
}

int ForReverse(int map[][100], const int endMap[][100], const bool flag[], int m, int n, int t)
{
    int max = 100000;//记录操作次数的最小值，设初值为100000，实际操作次数肯定比它小 
    int num = 0;
    int sum = 0;
    if (t == m-1)//递归执行或不执行翻转操作，直到到最后一行 
    {
        num = Judge(map, endMap, m, n, 0);//先不翻转，直接递归寻求最佳解 
        if (num != -1 && num < max)
            max = num;

        if (flag[t])//若能翻转，翻转，并递归寻求最佳解  
        {
            Reverse(map, t, n);
            ++sum;
            num = Judge(map, endMap, m, n, 0);
            if (num != -1 && num < max)
                max = num;
        }
        //返回无解或最佳解 
        if (max == 100000)
            return -1;
        return sum + max;
    }
    else//如果还未到最后一行，分别翻转和不翻转该行，比较返回的解，寻求最佳解 
    {
        num = ForReverse(map, endMap, flag, m, n, t+1);//先不翻转，直接递归处理下一行 
        if (num != -1 && num < max)
            max = num;
        
        if (flag[t])//若能翻转，翻转，并递归处理下一行 
        {
            Reverse(map, t, n);
            num = ForReverse(map, endMap, flag, m, n, t+1);
            if (num != -1 && num < max)
            {
                max = num;
                ++sum;
            }
        }
        //返回无解或最佳解 
        if (max == 100000)
            return -1;

        return sum + max;
    }
}

//递归执行交换列或不交换操作，寻求最佳解 
int Judge(int map[][100], const int endMap[][100], int m, int n, int t) 
{
    int max = 100000;
    int num = 0;
    if (t == n-1)//分析到最后一列，看是否相同，相同则返回操作次数0，否则无解返回-1 
    {
        if (EqualCel(map, endMap, m, t))
            return 0;
        else
            return -1;
    }
    else//还没有分析到最后一列，将该列与所有在其之右的列（包括自己）都交换一次，递归寻求最佳解 
    {
        for (int i=t; i<n; ++i)
        {
            SwapCel(map, m, t, i);//交换列t和列i 
        
            if (EqualCel(map, endMap, m, t))//如果第t列相同，递归分析下一列 
            {
                num = Judge(map, endMap, m, n, t+1);
                if (num != -1 && num < max)
                    max = num;
            }
            
            SwapCel(map, m, t, i);//再换回来 
        }
        //返回无解或最佳解 
        if (max == 100000)
            return -1;
        if (EqualCel(map, endMap, m, t))//没有执行交换 
            return max;
        else
            return max + 1;
    }
}


void Reverse(int map[][100], int row, int n)//翻转第row行 
{
    for (int i=0; i<n; ++i)
        map[row][i] = !map[row][i];
}

int Count(const int map[][100], int row, int n, int flag)//累积第row行值为flag的元素的数量 
{
    int sum = 0;
    for (int i=0; i<n; ++i)
        if (flag == map[row][i])
            ++sum;
            
    return sum;
}

void SwapCel(int map[][100], int m, int cel_1, int cel_2)//交换列t和列i 
{
    int temp;
    
    for (int i=0; i<m; ++i)
    {
        temp = map[i][cel_1];
        map[i][cel_1] = map[i][cel_2];
        map[i][cel_2] = temp;
    }
}

bool EqualCel(const int map[][100], const int endMap[][100], int m, int cel)//判断第t列是否相同 
{
    for (int i=0; i<m; ++i)
    {
        if (map[i][cel] != endMap[i][cel])
            return false;
    }
    return true;
}

/*算法实现题1-5 最大间隙问题
 
问题描述：
最大间隙问题：给定n 个实数x1, x2 ,..., xn，求这n 个数在实轴上相邻2 个数之间的最大差值。
假设对任何实数的下取整函数耗时O(1)，设计解最大间隙问题的线性时间算法。
 
编程任务：
对于给定的n 个实数x1,x2,...,xn，编程计算它们的最大间隙。

数据输入：
输入数据由文件名为input.txt的文本文件提供。文件的第1 行有1 个正整数n。接下来
的1 行中有n个实数 x1,x2,...,xn 。

结果输出:

程序运行结束时，将找到的最大间隙输出到文件output.txt中。
输入文件示例 输出文件示例
input.txt 
5
2.3 3.1 7.5 1.5 6.3

output.txt

3.2
*/
/*
算法思路：我的想法是先对数组排序，然后遍历数组找到最大间隙。
利用库函数对数组快排，时间复杂度为O（NlgN），遍历数组找最大间隙时间复杂度为O（N）。
没有理解假设对任何实数的下取整函数耗时O(1)的意思，所以没办法实现线性时间算法。 
表达能力有限，大家看代码，自己领会。 
*/
#include<iostream>
#include <time.h>
#include <math.h>

using namespace std;

double MaxInterstice(double a[], int n);

int main(int argc, char* argv[])
{
    time_t startTime;
    time_t endTime;

    time(&startTime);

    int n = 5;
    double a[50] = {2.3, 3.1, 7.5, 1.5, 6.3};

    cout << MaxInterstice(a, n) << endl;;

    time(&endTime);
    cout << "time = " << difftime(endTime, startTime) << endl;
    system("pause");
    return 0;
}
//---------------------------------------------------------------------------
static int Compare(const void *p1, const void *p2)
{
    double t =  (*(double *)p1) - (*(double *)p2);
    
    if (t > 0)
        return 1;
    else if (t < 0)
        return -1;
    else
        return 0;
}

double MaxInterstice(double a[], int n)
{
    qsort(a, n, sizeof(double), Compare);//对数组快排
    
    double d = 0;//存储最大间隙 
    for (int i=1; i<n; ++i)//遍历数组找最大间隙
    {
        if (a[i] - a[i-1] > d)
            d = a[i] - a[i-1];
    }
    
    return d;
}