程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 1850/ 1496 組合數學

POJ 1850/ 1496 組合數學

編輯:C++入門知識

POJ 1850/ 1496 組合數學

題目地址:
POJ 1496 Word Index
POJ 1850 Code

題意:
1. 每個詞是自增的
2. 同樣長度的詞是按字典序排練的
3. 我們把這些詞標序
求某個詞的序號

分析:
組合數學...
推出公式然後用楊輝三角打表出組合數,具體看http://blog.csdn.net/lyy289065406/article/details/6648492。
我還是太弱Orz...

代碼:

1496:

/*
*  Author:      illuz 
*  File:        1496.cpp
*  Create Date: 2014-05-24 23:38:54
*  Descripton:   
*/

#include 
#include 
#include 

const int N = 27;

int c[N][N], len, sum;
char str[11];

void init() {
	for (int i = 0; i < N; i++)
		for (int j = 0; j <= i; j++)
			if (!j || i == j)
				c[i][j] = 1;
			else
				c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
	c[0][0] = 0;
}

int main() {
	init();

	while (~scanf("%s", str)) {
		len = strlen(str);
		bool flag = true;
		for (int i = 1; i < len; i++)
			if (str[i - 1] >= str[i]) {
				puts("0");
				flag = false;
			}
		if (!flag)
			continue;

		sum = 1;
		for (int i = 1; i < len; i++) {
			sum += c[26][i];
		}

		for (int i = 0; i < len; i++) {
			char ch = (0 == i) ? 'a' : str[i - 1] + 1;
			while (ch <= str[i] - 1) {
				sum += c['z' - ch][len - i - 1];
				ch++;
			}
		}

		printf("%d\n", sum);
	}
	return 0;
}


1850:

/*
*  Author:      illuz 
*  File:        1850.cpp
*  Create Date: 2014-05-24 23:10:11
*  Descripton:   
*/

#include 
#include 
#include 

const int N = 27;

int c[N][N], len, sum;
char str[11];

void init() {
	for (int i = 0; i < N; i++)
		for (int j = 0; j <= i; j++)
			if (!j || i == j)
				c[i][j] = 1;
			else
				c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
	c[0][0] = 0;
}

int main() {
	init();

	scanf("%s", str);
	len = strlen(str);
	for (int i = 1; i < len; i++)
		if (str[i - 1] >= str[i]) {
			puts("0");
			return 0;
		}

	sum = 1;
	for (int i = 1; i < len; i++) {
		sum += c[26][i];
	}

	for (int i = 0; i < len; i++) {
		char ch = (0 == i) ? 'a' : str[i - 1] + 1;
		while (ch <= str[i] - 1) {
			sum += c['z' - ch][len - i - 1];
			ch++;
		}
	}

	printf("%d\n", sum);
	return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved