邮票面值设计

【问题描述】
【描述 Description 】

　　给定一个信封，最多只允许粘贴N张邮票，计算在给定M（N+M<=10）种邮票的情况下（假定所有的邮票数量都足够）,如何设计邮票的面值，能得到最大max ，使得1～max之间的每一个邮资值都能得到。 例如，N=3，M＝2，如果面值分别为1分、4分，则在l分～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）：如果面值分别为1分、3分，则在1分～7分之间的每一个邮资值都能得到。可以验证当N=3，M＝2时，7分就是可以得到连续的邮资最大值，所以MAX=7，面值分别为l分、3分。 【样例输入】 共一行，两个整数，分表为N与M的值。 【输入格式 Input Format 】 一行，分别为N,M。 【输出格式 Output Format 】 两行。 第一行为m种邮票的面值，按升序排列，各数之间用一个空格隔开。 第二行为最大值。 【样例输入 Sample Input 】 3 2 【样例输出 Sample Output 】 1 3 MAX=7 算法分析 深搜加DP 栈记录所用邮票的面值 每次面值的搜索的范围为：上一次使用的邮票面值+1 to 上一次连续达到的最大值+1 然后DP，记录达到每个面值用的最少邮票数，不断更新最优解 注意要从第1张邮票开始，否则要出错 【代码】 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

#include <stdio.h>
 
int a[11], ans[11];
int b[1001];
int n, m, max;
 
int dp(int i)
{
       int j, k;
 
       for (j = 1; j < 1001; j++)
              b[j] = 9999;
 
       for (j = 1; j <= i; j++)
              b[a[j]] = 1;
       j = 0;
 
       do
       {
              j++;
 
              for (k = 1; k <= i; k++)
                     if (j > a[k] && b[j - a[k]] + 1 < b[j])
                            b[j] = b[j - a[k]] + 1;
 
       }while (b[j] <= m);
       return j;
}
 
void search(int i)
{
       int j, k;
 
       if (i > n)
       {
              if (dp(i - 1) - 1 > max)
              {
                     for (j = 1; j <= 10; j++)
                            ans[j] = a[j];
                     max = dp(i - 1) - 1;
              }
              return;
       }
       j = dp(i - 1);
 
       for (k = j ; k >= a[i - 1] + 1; k--)
       {
              a[i] = k;
              search(i + 1);
       }
}
 
int main()
{
 
       int i;
       scanf("%d%d", &m, &n);
 
       max = 0;
       a[1] = 1;
       search(2);
 
       for (i = 1; i <= n; i++)
              printf("%d ", ans[i]);
 
       printf("\n");
       printf("MAX=%d\n", max);
       return 0;
}

YII框架中可以使用foreach遍历对象以及可以使用数组形式直接访问对象的原因

YII框架中可以使用foreach遍历对象以及可以使用数组形式直接访问对象的原因
在YII框架的使用过程中，我们可以使用foreach直接遍历findAll等方法返回的对象的属性
为什么呢？其实这与CModel实现的接口相关，接下来我们看下其实现的整个过程
对于一个我们定义的model，它会继承虚类CActiveRecord，CActiveRecord类继承于CModel，如下所示：

1
2
3
4

class special extends CActiveRecord {
}
abstract class CActiveRecord extends CModel{
}

最关键的地方是CModel类实现了IteratorAggregate接口。
而在CModel类中实现的getIterator方法返回的是这个model的所有属性，使用的迭代器是Yii框架实现的CMapIterator，而CMapIterator实现了Iterator接口

1
2
3
4
5
6
7
8
9
10

/**
* Returns an iterator for traversing the attributes in the model.
* This method is required by the interface IteratorAggregate.
* @return CMapIterator an iterator for traversing the items in the list.
*/
public function getIterator()
{
$attributes=$this->getAttributes();
return new CMapIterator($attributes);
}

这些就使得我们可以使用foreach直接遍历findAll等方法返回的对象
关于此迭代器可以参看之前写的关于迭代器的文章：
PHP源码阅读笔记二十四 ：iterator实现中当值为flase时无法完成迭代的原因分析

关于IteratorAggregate接口请移步
http://cn.php.net/manual/en/class.iteratoraggregate.php
关于Iterator接口请移步
http://cn.php.net/manual/en/class.iterator.php

同样的道理，
因为CModel实现了ArrayAccess接口，所以可以直接访问以数组的方式访问
关于ArrayAccess接口请移步
http://cn.php.net/manual/en/class.arrayaccess.php

PHP中大整数相乘的2种实现方式

PHP中大整数相乘的2种实现方式
1、【通过调用BCMath实现】
PHP 为任意精度数学计算提供了二进制计算器（Binary Calculator），它支持任意大小和精度的数字，以字符串形式描述。
示例代码如下：

1
2
3
4
5
6

<?PHP
$op_left = '123456789123456789';                                                                                  
$op_right = '123456789123456789';
$rs = bcmul($op_left, $op_right);
var_dump($rs);
die();

2、【通过字符串数组相乘实现】
将乘数和被乘数分别按指定的位数存放到数组中，然后再模拟乘法，将结果加起来，最后在返回的时候针对不够位数的进行补0操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

<?PHP
define('DEPTH', 10000);
define('LEN', strlen(DEPTH) - 1);
 
/**
 * 格式化数组元素，如果单个元素的值不够LEN的长度，前面补0
 * @param string $input
 */
function item_format(&$input) {
    $input = str_pad($input, LEN, "0", STR_PAD_LEFT);
}
 
/**
 * 初始化相乘的字符串，将其转化成数组
 * @param string $input 需要相乘的操作数
 * @return array 已经分好块，并且逆转了的数组
 */
function init_array($input) {
    $begin_len = strlen($input) % LEN;
    $a = array();
    if ($begin_len > 0) {
        $a[0] = substr($input, 0, $begin_len);                                                                         
        $input = substr($input, $begin_len);
    }
    $a = array_merge($a, str_split($input, LEN));
    return array_reverse($a);
}
/**
 * 大整数相乘的数组实现
 * @param string $left_operand  左边的操作数
 * @param string $right_operand 右边的操作数
 * @return string   相乘的结果
 */
function mul($left_operand, $right_operand) {
    if (empty($left_operand) || empty($right_operand)) {
        return FALSE;
    }
 
    /* 初始化相乘的数组 */
    $a = init_array($left_operand);
    $b = init_array($right_operand);
    $len_a = strlen($a);
    $len_b = strlen($b);
 
    for ($i = 0; $i < $len_a; $i++) {
        for ($j = 0; $j < $len_b; $j++) {
            $c[$i + $j] += $a[$i] * $b[$j];
            if ($c[$i + $j] >= DEPTH) { //  进位操作
                $c[$i + $j + 1] += floor($c[$i + $j] / DEPTH);
                $c[$i + $j] %= DEPTH;
            }
        }
    }
 
    $c = array_reverse($c);
    array_walk(&$c, 'item_format');
    return ltrim(implode('', $c), '0');
}
$left_operand = '123456789123456789';
$right_operand = '123456789123456789';
$rs = mul($left_operand, $right_operand);
var_dump($rs);

EOF