非递减字符串问题

如题：

       在非递减字符串中，从左到右的字符依次按ASC码非递减排列，例如 abcd,aaaa,aabb等等，现在假设字符串由a-j等10个字符串组成，请你确定特定长度的非递减字符串的数目。

 

 

算法思想：当我显现看到这个题，有些迷惑，为什么是十个字符串呢，，后才自然想到对应十个阿拉伯数字0-9.

               问题就可以从这个地方解决。把某个长度的串看成是一个整数，想办法取出这个整数的每一个具体的位，然后进行  比较不就可以判断是否复合条件，比如给定的长度为4，我就从0000遍历到9999，找出复合条件的整数然后计数，不就可以了吗。这个方法效率肯定会比较低，而且如果刚给的字母的个数超过10，就不能用这个办法了。。。。不知道还有什么其他好的办法？

 

下面是我实现的代码--简单

 

#include<stdio.h>
#include <stdlib.h>

int  exp(int i) 
{
	int res=1;
	int j=0;
	while(j<i)
	{
       res*=10; 
	   j++;
	}
	return res;
}

void getBit(int str[],int data,int l) //获取整数中每一个位
{
	for(int i=0;i<l;i++)
	{
		str[i]=0;
	}
	for(int j=0;j<l;j++) 
	{
		str[j]=(data%exp(j+1))/exp(j);
	}
}
int isSort(int str[],int l)  //判断是否非递减
{
	for(int i=0;i<l-1;i++)
	{
		if(str[i]<str[i+1])
		{
			return 0;
		}
	}
	return 1;
}
void main()
{
	int l=4;//字符串长度
	int count=0;//计数
	printf("please input a len of str\n");
	scanf("%d,%d",&l);
    printf("\n");
	int data=0;//长度为l的最大整数
	int *bit=(int*)malloc(sizeof(int)*l);;

	for(int i=0;i<l;i++)
	{
        data+=exp(i)*9;  
	}
	for(int j=0;j<=data;j++)
	{
		getBit(bit,j,l);
		if(isSort(bit,l)==1)
		{
			count++;
		}
	}
	free(bit);
	printf("%d\n",count);
}

评论

2 楼 zxxapple 2012-02-16  

ZaneLee007 写道

可重复的排列组合问题吧？和数字没什么关系

恩 是的  ，上边只是一个特例的简单实现

1 楼 ZaneLee007 2012-02-16  

可重复的排列组合问题吧？和数字没什么关系