Code Bye

求相邻数字组合的种类(算法)

 

给定一组数字,相邻两个数组组合,组合的数不能超过26.问有多少种组合。
例如:给一个数字23,可以为2,3和23两种组合。

没太明白题意, lz想说只有两个相邻 的数才可以组合吗?
比如 2345, 可以有2, 3, 4, 5, 23, 34, 45,…..但是24就算错误?
那lz可以直接排序, 然后从第一个数开始输出连续一个, 连续两个:
for(int i=0; i<a.length. ++i){       // 确定输出上界
    for(int j=i; j<a.length; ++j){    // 确定输出下界
        if( i - j >= 26 ){
            break;
        }
        for(int k=i; k<=j; ++k){     // 输出i, j直接的内容
            System.out.println(a[k]);
        }
    }
}

或者向2, 3, 4, 5, 23, 34, 45,…这样,先输出长度为一的,在输出长度为二的….只有有一定规律就行

引用 1 楼 u011004037 的回复:

没太明白题意, lz想说只有两个相邻 的数才可以组合吗?
比如 2345, 可以有2, 3, 4, 5, 23, 34, 45,…..但是24就算错误?
那lz可以直接排序, 然后从第一个数开始输出连续一个, 连续两个:

for(int i=0; i<a.length. ++i){       // 确定输出上界
    for(int j=i; j<a.length; ++j){    // 确定输出下界
        if( i - j >= 26 ){
            break;
        }
        for(int k=i; k<=j; ++k){     // 输出i, j直接的内容
            System.out.println(a[k]);
        }
    }
}

或者向2, 3, 4, 5, 23, 34, 45,…这样,先输出长度为一的,在输出长度为二的….只有有一定规律就行

2345的组合只能是{2,3,4,5},{23,45},{2,3,45},{2,34,5},{23,4,5},但是其中第2,3,4种有超过26的元素。不符合要求。只有第1,5两种组合成立

说一个思路,如果有bug的话告诉我一声,我也没考虑全面:
首先,解决一个问题,就是说一串数究竟能有多少1位和两位数的组合方式。(后面均是建立在相邻的基础上)设里面有x个1位的,y个2位的,数字长度为n。那么x+2y=n(0=<x=<n,x,y只能取整数)这是一层循环,内层我们考虑对x个1位和y个2位有多少种组合方式,如1122,2211,2112,2121…我们有x+y个位置,其中x个1,y个2,用组合就能得到x的位置有多少种。(C下标:x+y,上标:x)剩下的就是y的位置。遍历所有可能的x取值得到一串数的1位和2位的所有组合方式数目。我们使解决这个问题的方法签名为f(n)
然后 ,遍历一下数字每一位找出大于26的组合,对组合内的所有内容进行下面的运算,比如数字是1238290,38大于26,前面有2位,后面有3位,我们计算f(2)+f(3)…把这些结果加起来得到sum
最后 f(n)-sum就是我们要的组合数
人家要具体输出,你给方法数,不管对不对,题目就没看清。
另外,我看楼主的意思,应该是给一堆,从小到大排序后,dfs写法就可以了。

void dfs(int index, int cnt) {
    if (index >= all) {//all为所有数的总和
        将ans放入最终结果
        return;
    }
    ans[cnt + 1] = index;
    dfs(index + 1, cnt + 1);
    if (num[index + 1] == num[index]  + 1) {
        ans[cnt + 1] = 10 * num[index] + num[index + 1];
        dfs(index + 2, cnt + 1);
    }
}
上面是伪代码

引用 4 楼 ningbohezhijun 的回复:

人家要具体输出,你给方法数,不管对不对,题目就没看清。
另外,我看楼主的意思,应该是给一堆,从小到大排序后,dfs写法就可以了。

void dfs(int index, int cnt) {
    if (index >= all) {//all为所有数的总和
        将ans放入最终结果
        return;
    }
    ans[cnt + 1] = index;
    dfs(index + 1, cnt + 1);
    if (num[index + 1] == num[index]  + 1) {
        ans[cnt + 1] = 10 * num[index] + num[index + 1];
        dfs(index + 2, cnt + 1);
    }
}
上面是伪代码

不要排序。不要改变数字的顺序。

额, 如果只是求数量, 那么可以使用这个:
for( int i=0; i<a.length; ++i ){
	if( a[i] < 3 ){
		count++;
	}
	else if( a[i] < 7 ){
		b[j] = count + 1;
		count = 0;
		j++;
	}
	else if( count != 0 ){
		b[j] =  count;
		count = 0;
		j++;
	}
}
int result = 1;
for( int i=0; i<j; i++ ){
	result *= b[i];
}

result就是种类数

少了几句初始化:
int a[] = { 2, 3, 4, 5 };
int b[] = new int[a.length];
int count = 0;
int j = 0;
如果需要打印所有序列, 则可以使用动态规划,
public static void main(String[] argc){
	int a[] = { 2, 1, 2, 3, 4, 5, 1, 2 };
	print(a, 0, "");
}
public static void print(int[] a, int origin, String prefix){
	if(origin < a.length-1){
		prefix = ( prefix.equals("") ? "" : prefix+", " );   // 添加逗号分隔数字

		print(a, origin+1, prefix+a[origin]);

		if(a[origin]*10 + a[origin+1] <= 26){
			print(a, origin+2, prefix+a[origin]+a[origin+1]);
		}
	}
	else if(origin == a.length-1 ){		// 还剩一个直接加到队尾即可
		System.out.println( prefix + "," + a[origin] );
	}
	else{
		System.out.println( prefix );
	}
}
引用 6 楼 u011004037 的回复:

额, 如果只是求数量, 那么可以使用这个:

for( int i=0; i<a.length; ++i ){
	if( a[i] < 3 ){
		count++;
	}
	else if( a[i] < 7 ){
		b[j] = count + 1;
		count = 0;
		j++;
	}
	else if( count != 0 ){
		b[j] =  count;
		count = 0;
		j++;
	}
}
int result = 1;
for( int i=0; i<j; i++ ){
	result *= b[i];
}

result就是种类数

代码没看的很明白,不过我运行了一下,举个特殊的例子{2,1,1,2,3},跑出来的结果是5.现在我们来列举一下可能性:1_{2,1,1,2,3}     2_{21,1,2,3}   3_{21,12,3}   4_{21,1,23}   5{2,1,12,3}   6_{2,1,1,23}….明显不只是有5个的

这个例子不算特殊, 是我忘了, 上课的时候还记得, 下课就忘了….
public static void main(String[] argc){
	int a[] = {2,1,1,2,3};
	int b[] = new int[a.length];
	int count = 0;
	int j = 0;
	for( int i=0; i<a.length; ++i ){
		if( a[i] < 3 ){
			count++;
		}
		else if( a[i] < 7 ){
			b[j] = count + 1;
			count = 0;
			j++;
		}
		else if( count != 0 ){
			b[j] =  count;
			count = 0;
			j++;
		}
	}
	int result = 1;
	for( int i=0; i<j; i++ ){
		result *= conver(b[i]);
	}
	System.out.println(result);
}
public static int conver(int i){   // 契科夫数列
	if( i < 3 ){
		return i;
	}
	return conver(i-1) + conver(i-2);
}
额, 又错了:
for( int i=0; i<a.length; ++i ){
	if( a[i] < 3 ){
		count++;
	}
	else if( (a[i]<7) || (i>0 && a[i-1]<2) ){
		b[j] = count + 1;
		count = 0;
		j++;
	}
	else if( count != 0 ){
		b[j] =  count;
		count = 0;
		j++;
	}
}
if( count != 0 ){
	b[j] = count;
	j++;
}

是这样的, 我们需要将整个数组划分成若干个部分, 每个部分符合这样的规则:
前面的数小于等于2, 如果倒数第二个数为1, 那么最后一个数为3-9, 如果倒数第二个数为2, 那么最后一个数为3-6, 写成正则就是:
[0-2]* ( [01][3-9] | 2[3-6] )
然后求这个部分的长度. 
这个部分的任意两个相邻的数都可以组合, 所以整个数字串的组合数就是这些片段的组合数的乘积,
那么问题就变成求连续的n个数有几种组合了, 这个可以使用 f(n) = f(n-1) + f(n-2) 来计算, 就是契科夫数列
为什么是这个数列, lz可以参见8楼的代码, 

11L讲的对
解释一下为什么是斐波那契数列,如果我们要知道5个数字的组合方式,5个数字可以由3个数字的任意组合加上一个2位数字(4,5位组合)也可以由4个数字的任意组合加上一个1位数字(第5位)。5个数字的组合方式有f(5)种,4个数字的组合f(4)种,3个数字的组合f(3)种,所以f(5)=f(4)+f(3)
引用 11 楼 u011004037 的回复:

额, 又错了:

for( int i=0; i<a.length; ++i ){
	if( a[i] < 3 ){
		count++;
	}
	else if( (a[i]<7) || (i>0 && a[i-1]<2) ){
		b[j] = count + 1;
		count = 0;
		j++;
	}
	else if( count != 0 ){
		b[j] =  count;
		count = 0;
		j++;
	}
}
if( count != 0 ){
	b[j] = count;
	j++;
}

是这样的, 我们需要将整个数组划分成若干个部分, 每个部分符合这样的规则:
前面的数小于等于2, 如果倒数第二个数为1, 那么最后一个数为3-9, 如果倒数第二个数为2, 那么最后一个数为3-6, 写成正则就是:
[0-2]* ( [01][3-9] | 2[3-6] )
然后求这个部分的长度. 
这个部分的任意两个相邻的数都可以组合, 所以整个数字串的组合数就是这些片段的组合数的乘积,
那么问题就变成求连续的n个数有几种组合了, 这个可以使用 f(n) = f(n-1) + f(n-2) 来计算, 就是契科夫数列
为什么是这个数列, lz可以参见8楼的代码, 

你说的一部分我能理解。的确不管怎么分组,“前面的数小于等于2”。但是为什么“ 如果倒数第二个数为1, 那么最后一个数为3-9” ?数字是可以重复使用。也就是说“11”这种组合是可以存在的。同理“如果倒数第二个数为2”的话也应该可以重复使用的。

40分
额, 我的意思是找出如下的序列
1212225   或者  1211212219
就是说, 最后两个数 ( 25  或者 19 ) 小于等于 26, 且最后一个数大于3, 比如 ( 5 , 9 ), 这就意味着, 这几个数是一组, 不管后面怎么添加字符, 都不能和最后一个数组合.
那么, 整个数字串就会被分为若干个孤立的片段, 比如这样:
1123  2218  8  7 18 
那么, 他们有多少种组合呢?
由于1123里面的任意两个相邻的数都可以组合, 而 第一组最后的3和第二组第一个2大于26, 是不能组合的, 同理这里的每个数字只能和同组的相邻数的组合,
那么, 再往下就是高中数学的东西了:
1123有5种写法(1, 1, 2, 3)  (11, 2, 3)  (1, 12, 3)  (1, 1, 23)  (11, 23)
2218也有5中写法
8有一种写法( 8 )
7有一种写法
18 有俩种写法 (1, 8) (18)
那么这个数字串又多少种写法?
引用 14 楼 u011004037 的回复:

额, 我的意思是找出如下的序列
1212225   或者  1211212219
就是说, 最后两个数 ( 25  或者 19 ) 小于等于 26, 且最后一个数大于3, 比如 ( 5 , 9 ), 这就意味着, 这几个数是一组, 不管后面怎么添加字符, 都不能和最后一个数组合.
那么, 整个数字串就会被分为若干个孤立的片段, 比如这样:
1123  2218  8  7 18 
那么, 他们有多少种组合呢?
由于1123里面的任意两个相邻的数都可以组合, 而 第一组最后的3和第二组第一个2大于26, 是不能组合的, 同理这里的每个数字只能和同组的相邻数的组合,
那么, 再往下就是高中数学的东西了:
1123有5种写法(1, 1, 2, 3)  (11, 2, 3)  (1, 12, 3)  (1, 1, 23)  (11, 23)
2218也有5中写法
8有一种写法( 8 )
7有一种写法
18 有俩种写法 (1, 8) (18)
那么这个数字串又多少种写法?

我大概明白你的意思了。大概就是把整个数字串,分成若干个不含有超过26的有效的基础数字串。然后再简单算出每一个不用考虑超过26的情况的相邻数字的全组合数。再进行相乘就是有效的 小于26的组合数


CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明求相邻数字组合的种类(算法)