杰拉斯的博客
JavaScript农历转换类
杰拉斯 | 时间:2013-01-24, Thu | 8,890 views前端开发
今天在做项目的时候需要用到JavaScript农历转换算法,从网上搜索并整理了一下,重新写出一个JavaScript农历转换类,不敢独占,特此与大家分享。
经典回溯算法问题:九宫格
杰拉斯 | 时间:2012-12-18, Tue | 22,301 views编程算法
九宫格是在81个格子中,要满足以下条件:(1)每个横行和竖列中的9个格子都包含数字1至9,不重复;(2)每个黑色粗实线围住的9个格子都包含数字1至9,不重复。如下表所示:
7 6 1 9 3 4 8 2 5 3 5 4 6 2 8 1 9 7 9 2 8 1 5 7 6 3 4 2 1 9 5 4 6 3 7 8 4 8 3 2 7 9 5 1 6 5 7 6 3 8 1 9 4 2 1 9 5 7 6 2 4 8 3 8 3 2 4 9 5 7 6 1 6 4 7 8 1 3 2 5 9
要求找出给定数字的九宫格。
【输入形式】
输入9行9列81个数字,其中0表示要填的数字。
【输出形式】
输出满足条件的九宫格。
【输入样例】
0 6 1 0 3 0 0 2 0 0 5 0 0 0 8 1 0 7 0 0 0 0 0 7 0 3 4 0 0 9 0 0 6 0 7 8 0 0 3 2 0 9 5 0 0 5 7 0 3 0 0 9 0 0 1 9 0 7 0 0 0 0 0 8 0 2 4 0 0 0 6 0 0 4 0 0 1 0 2 5 0
【输出样例】
7 6 1 9 3 4 8 2 5 3 5 4 6 2 8 1 9 7 9 2 8 1 5 7 6 3 4 2 1 9 5 4 6 3 7 8 4 8 3 2 7 9 5 1 6 5 7 6 3 8 1 9 4 2 1 9 5 7 6 2 4 8 3 8 3 2 4 9 5 7 6 1 6 4 7 8 1 3 2 5 9
代码及思路如下:
#include<stdio.h> bool canFill(int a[9][9], int k, int n){ int i, j, row = k / 9, col = k % 9; for(i = 0; i < 9; ++i){ if(a[i][col] == n){ return false; } } for(j = 0; j < 9; ++j){ if(a[row][j] == n){ return false; } } for(i = row - row % 3; i < row - row % 3 + 3; ++i){ for(j = col - col % 3; j < col - col % 3 + 3; ++j){ if(a[i][j] == n){ return false; } } } return true; } void fill(int a[9][9], int k = 0){ int i, j; if(k == 81){ for(i = 0; i < 9; ++i){ for(j = 0; j < 9; ++j){ printf("%d ", a[i][j]); } printf("\n"); } return; } int row = k / 9, col = k % 9; if(a[row][col] == 0){ for(i = 1; i <= 9; ++i){ if(canFill(a, k, i)){ a[row][col] = i; fill(a, k + 1); a[row][col] = 0; } } }else{ fill(a, k + 1); } } int main(){ int i, j, a[9][9]; for(i = 0; i < 9; ++i){ for(j = 0; j < 9; ++j){ scanf("%d", &a[i][j]); } } fill(a); return 0; }
2013年5月4日3点温习重写代码如下:
#include<stdio.h> int square[9][9]; int isEnabled(int k, int num){ int row = k / 9; int col = k % 9; for(int i = 0; i < 9; ++i){ if(square[row][i] == num || square[i][col] == num){ return false; } } int m = row - row % 3; int n = col - col % 3; for(int i = m; i < m + 3; ++i){ for(int j = n; j < n + 3; ++j){ if(square[i][j] == num){ return false; } } } return true; } void fill(int k = 0){ int row = k / 9; int col = k % 9; if(k >= 81){ for(int i = 0; i < 9; ++i){ for(int j = 0; j < 9; ++j){ printf("%d ", square[i][j]); } printf("\n"); } return; } if(square[row][col] > 0){ fill(k + 1); return; } for(int i = 1; i <= 9; ++i){ if(isEnabled(k, i)){ square[row][col] = i; fill(k + 1); square[row][col] = 0; } } } int main(){ for(int i = 0; i < 9; ++i){ for(int j = 0; j < 9; ++j){ scanf("%d", &square[i][j]); } } fill(); return 0; }
经典算法:整数划分问题
杰拉斯 | 时间:2012-12-12, Wed | 30,598 views编程算法
整数划分问题(算法分析与设计 P12):将正整数n表示成一系列正整数之和:n=n1+n2+…+nk,其中n1≥n2≥…≥nk≥1,k≥1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数和方案。例如正整数6有如下11种不同的划分:
6 5+1 4+2, 4+1+1 3+3, 3+2+1, 3+1+1+1 2+2+2, 2+2+1+1, 2+1+1+1+1 1+1+1+1+1+1
[小技巧]如何得到C语言中int最大值
杰拉斯 | 时间:2012-10-29, Mon | 16,847 views编程算法
只需一小句代码,如下:
printf("%d\n", ~(unsigned int)0 / 2);
分析:
当无符号0以二进制储存在内存中的时候,每一位都为0,以32位int为例,(unsigned int)0的二进制为:
00000000000000000000000000000000
按位取反(~)后,变成:
11111111111111111111111111111111
此时的十进制为:
4294967295
除以2(因为int类型中有一半表示负数且比正数多一个)之后为:
2147483647
即为32位int类型最大值。
[ACM_HDU_3177]Crixalis's Equipment
杰拉斯 | 时间:2012-07-25, Wed | 26,109 views编程算法
Crixalis's Equipment
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1350 Accepted Submission(s): 543
Description
Crixalis - Sand King used to be a giant scorpion(蝎子) in the deserts of Kalimdor. Though he's a guardian of Lich King now, he keeps the living habit of a scorpion like living underground and digging holes.
Someday Crixalis decides to move to another nice place and build a new house for himself (Actually it's just a new hole). As he collected a lot of equipment, he needs to dig a hole beside his new house to store them. This hole has a volume of V units, and Crixalis has N equipment, each of them needs Ai units of space. When dragging his equipment into the hole, Crixalis finds that he needs more space to ensure everything is placed well. Actually, the ith equipment needs Bi units of space during the moving. More precisely Crixalis can not move equipment into the hole unless there are Bi units of space left. After it moved in, the volume of the hole will decrease by Ai. Crixalis wonders if he can move all his equipment into the new hole and he turns to you for help.
Input
The first line contains an integer T, indicating the number of test cases. Then follows T cases, each one contains N + 1 lines. The first line contains 2 integers: V, volume of a hole and N, number of equipment respectively. The next N lines contain N pairs of integers: Ai and Bi.
0
Output
For each case output "Yes" if Crixalis can move all his equipment into the new hole or else output "No".
Sample Input
2 20 3 10 20 3 10 1 7 10 2 1 10 2 11
Sample Output
Yes No