这样的一个需求的实现

Posted by 机器人 on 29th 六月 2009 in php/javascript

需求:

一个表格的单元格所对应的坐标由字母组合而成,具体排列方式如下:

第  1  行: A          B         C          D           E      …..     Z
第  2  行:AA       AB      AC      AD        AE   …..    AZ
第  3  行: BA       BB       BC      BD        BE    …..    BZ


第 27 行:ZA       ZB       ZC       ZD        ZE  …..     ZZ
第 28 行:AAA   AAB    AAC   AAD   AAE …    AAZ
依次类推
….
….

分别由26个英方字母组合而成,而每一个单元格都由唯一的一个数字与其对应,如:1 对应第1行第一列的A,26对应第1行第26列的Z,27对应第2行第1列的AA,26 * 27 = 702对应第27行26列的ZZ,703对应第28行第1列的AAA,等等。

请编写一个函数,接受一个数字参数,然后返回该数字所对应的单元格的字母组合。

分析:

由上面的需求可知,表格只有26列,而行数没有限制,数字26对应Z,27则对应AZ了,从而可以看出,列只要到了26,再加1的话,行就需要扩展一位。所以可以把这个问题看成是求26进制数的问题,即,怎么将一个十进制转换成一个26进制数。

所以第一步只需要请求出给出数字所对应26进制数即可,对于求26进制的方式和求一个十进制数的二进制的方式类似,通过不停的求商取余,直接到最后的商为0,然后对余数取反。

第二步则是建立一个字母和数字的映射数组,然后将第一步所求得的26进制数映射成对应的字母即可。

大致实现方法如下:

$a = array();
$a = array();
do {
    $n = $num % 26;
    $num = (int)($num / 26);
    array_push($a,$n);
} while ($num != 0);
$a = array_reverse($a)

将所取得的余数全部放入数组,等求解结束后,再将保存余数的数据里的元素反转。

接下来选建立一个映射数组。

$map = array(
	 0 => 'Z', 1 => 'A', 2 => 'B', 3 => 'C', 4 => 'D',
	 5 => 'E', 6 => 'F', 7 => 'G', 8 => 'H', 9 => 'I', 
	10 => 'J',11 => 'K',12 => 'L',13 => 'M',14 => 'N',
	15 => 'O',16 => 'P',17 => 'Q',18 => 'R',19 => 'S',
	20 => 'T',21 => 'U',22 => 'V',23 => 'W',24 => 'X',
	25 => 'Y'
);

但很快就会发现一个这样的规律。
25 对应的26进制数为 0 25, 映射字母为 ZY
26 对应的26进制数为 1 0, 映射字母为 ZA
27 对应的26进制数为 1 1, 映射字母为 AA
702对应的26进制数为 1 1 0,映射字母为 AAZ
703对应的26进制数为 1 1 1,映射字母为AAA
由上面的分析结果,可知,下面两种情况的映射结果不正确。

1.所有能被26整除的数所对应的字母对应关系不正确,而这样的数在被转成26进制数时,最后一数都为0,次最后一位数为1。

2.所有第一行内的数字对应的十进制数也不正确,最高位都为0,如果把最高位的0去掉,对应关系就正确了。

对于第一种情况,仔细观察可以发现,数据不正确,是因为数字刚才被26整除,需要进位所引起的,如果把进的位再退一位,就会发现对应关系就看起来对多了,可能还是有些地方不对。
如:
本来26应该对应Z的,而现在对应的是ZA,假设上面的分析结果正确,那么先对26所对应的26进制数进行退位分析。26对应的26进制数为1 0,由上面可知,高位的1是由于数字刚好被整除进位引起的,所以需要对其进行退位减1。
1 0 -> 0 0。
同样的分析方法来分析 702。
1 1 0 -> 1 0 0。
似乎看来起来还是不正确,但我们再仔细一看就发现了,这里是由于进行两次进位引起的,所以也需要进行两次即位。即。
1 1 0 -> 1 0 0 -> 0 0 0.
这下看起来似乎就正确很多了。这里的结果似乎和第一行内的数字结果很相似,如果将最高位的0去掉,结果就正确了。
于是,暂时得出如下结论:
结论 1: 如果转换后的26进制数中有0,需要对其次高位减1,次高位不存在时,则不进行任何操作。
结论 2: 如果转换后的26进制数中最高位为0,则需要将该位删除。

对于上面的几特殊情况运行上面的两条结论:
就可以得出正确结论。

大致实现代码如下:

$cnt = count($a);
for ($i = 0; $i < $cnt; $i++) {
		//将0所在位的次高位减1
    if ($a[$i] == 0 && isset($a[$i+1])) {
        $a[$i+1] -= 1;
    }
    //映射字母
    $a[$i] = $map[$a[$i]];
}
//最高位为0时,将其删除。由于已经做了映射转换,0转换为了Z
if ($a[$cnt -1] == 'Z') unset($a[$cnt-1]);

结合上面的分析,完全实现如下:

function num2name($num) {
	$map = array(
		 0 => 'Z', 1 => 'A', 2 => 'B', 3 => 'C', 4 => 'D',
		 5 => 'E', 6 => 'F', 7 => 'G', 8 => 'H', 9 => 'I', 
		10 => 'J',11 => 'K',12 => 'L',13 => 'M',14 => 'N',
		15 => 'O',16 => 'P',17 => 'Q',18 => 'R',19 => 'S',
		20 => 'T',21 => 'U',22 => 'V',23 => 'W',24 => 'X',
		25 => 'Y'
	);    
    $a = array();
    do {
        $n = $num % 26;
        $num = (int)($num / 26);
        array_push($a,$n);
    } while ($num != 0);
    $cnt = count($a);
    for ($i = 0; $i < $cnt; $i++) {
        if ($a[$i] == 0 && isset($a[$i+1])) {
            $a[$i+1] -= 1;
        }
        $a[$i] = $map[$a[$i]];
    }
    if ($a[$cnt -1] == 'Z') unset($a[$cnt-1]);
    $a = array_reverse($a);
    return join("",$a);
}

测试代码

$d = array(702,703,25,3234,24,1324,314,128,2,41);
foreach($d as $v) {
    echo num2name($v)."\n";
}

测试如果

ZZ
AAA
Y
DTJ
X
AXX
LB
DX
B
AO

另外附上一种运用递归的实现方法。(网友提供)

function num2name($num) {
    //定义一个数组
    if($num==0) return '';
    $arr ='ZABCDEFGHIJKLMNOPQRSTUVWXY';
    $n = intval(($num-1)/26); //取得整数倍
    $m = $num%26; //取得余数
    $name = num2name($n).$arr{$m};
    return $name;
}

哈哈,好像这种方式简洁多了!
机器人 2009-06-29 16:16 于 北京 晴

分享到: 新浪微博

3 Responses to “这样的一个需求的实现”

  1. 小黑米 说:

    我的解法: 思路都差不多的
    function num2name($x) {
    $arr = array ();

    while ( intval ( ($x – 1) / 26 ) ) {
    array_unshift ( $arr, ($x – 1) % 26 ); //入栈
    $x = intval ( ($x – 1) / 26 );
    }
    array_unshift ( $arr, ($x – 1) % 26 );

    foreach ( $arr as $v ) { //出栈
    echo sprintf ( “%c”, $v + 97 ); //把asiic转成字母,97为“a”
    }

    }
    $d = array(702,703,25,3234,24,1324,314,128,2,41,43324,243213,21341134,112344,10000);
    foreach($d as $v) {
    num2name($v);
    echo “\r”;
    }

  2. 机器人 说:

    array_unshift这个函数用的妙啊,我用了array_push和array_reverse这两个函数来实现的。

  3. 小黑米 说:

    你的那个do{}while()也用的巧~ 我忘记了do{}while()的存在…

Leave a Reply