网友如下求助:如何分配总租值为2700的三个房间,使三人都满意。如果是两个人分得话,马上就想到了“小熊分蛋糕”的问题。 说熊妈妈两个熊宝宝一块蛋糕,一个合理的分割方案是:宝宝1切蛋糕,宝宝2选择蛋糕。此方案有一个妙处在于,博弈双方各占优势,又各占劣势,宝宝1切割的优势与选择的劣势的结合使得他必须尽可能降低其切割优势,因为他必须对他的切割劣势埋单,即切割尽可能平均。这样的结果就是:切割方不在具有优势,选择方就也丧失了劣势,因为前者已经放弃了优势(因为他选择尽可能平均分配),使得他的选择的优势也失去了意义。最终的结果是:该分配双方均不占优势,双方均觉得公平。利用这个方案,可以很好的解决两个人分割利益\责任的问题,我们只需使一方为划分者,另一方为选择方就可以了。

显然,这个方案只能局限与两人分割情形。那么对于多人分割又当如何处理呢?

这里先说一下上述问题的升级版:假设熊妈妈给了宝宝们两块味道不同的蛋糕,一个合理的分割方案是:宝宝1切蛋糕1,宝宝2切蛋糕2,切某一蛋糕的宝宝就会丧失那次切割的选择权,即:宝宝2在选择蛋糕1的部分具有优先权,宝宝1在选择蛋糕2的部分具有优先选择权。如果两个宝宝的口味一致,即蛋糕对他们来说具有相同价值,那么就把问题转化为了两个基本分蛋糕的问题。 如果两个宝宝对蛋糕喜好的口味不一致,那么博弈的结果可能就是宝宝各会分得自己喜爱的完整蛋糕。

此问题可以衍生出一个现实问题:A,B公同租总价为p两房间房子。那么一个合理的分割方案为:A,B分别提供自己的定价方案:假设A对两房子的定价分别为 $a_1,a_2(a_1+a_2=p)$;同理B对两房子的定价分别为$b_1,b_2$.则我们做以下计算:$p_1=(a_1+b_1)/2;p_2=(a_2+b_2)/2$;此时,两房子的定价即为$p_1,p_2$且满足$p_1+p_2=p$。那么房子如何分配呢?$a_1,b_1$中的大值者来负责$p_1,a_2,b_2$中的大值者来负责$p_2$.可以证明,该方案是一种很合理的分个方案。

那么对于更多个参与者,怎么处理,只需对上述过程拓展,即得到通解: 对n个人分担\负责价值p(分为n个子部分)的问题来说,解决方案: 第i个人对k部分的估价为:$x_{ik}$其中: $$ \sum_{k=0}^{n}{x_{ik}} = p $$ 那么我们对第k部分的定价为: $$ p_k = \sum_{i=0}^n{p_{ik}} / n $$ 此时,所有部分的总价仍为p: $$ \sum_{k=0}^{n}{p_k} = \sum_{k=0}^n\sum_{i=0}^n{p_{ik}} / n = \sum_{i=0}^n\sum_{k=0}^n{p_{ik}} / n = \sum_{i=0}^np / n = p $$ 不仅如此,此方案的精妙之处在于很离的分配。价钱确定以后,怎么分配? 分配规则很SIMPLE:对没一间部分出价最高的拥有该部分的,要对该部分付费。这里利用了一个博弈心理:如果你想拥有一个部分K,那么你就要出足量的钱来保证在所有人里出钱最多,这样的事件有两面性:一方面,你会拥有最爱的部分;另一方面,你要付出足量的钱来保证。二者作用的结果就是使参与者投出自己认为合适的钱到合适的部分上,最终的分配结果不会有抱怨不公平方:因为每个参与者都有权力决定分配结果,对结果不满意,只能怪自己。付出越大,收获希望越大,投入产出成正比,所以积极的方案.

对于结构复杂代码,VIM折叠功能对于思路清晰化、代码结构可读化,均有奇效。

我所用的有效的折叠方案:

set menthod=manual

对于代码:

example.c
1
2
3
4
5
6
#include <stdio.h>
int main()
{
	printf("Hello World\n");
	return 0;
}
使用Esc + Shift + v进入 visual 模式
然后number + j选定要折叠的行
使用s + f折叠选定的行
展开折叠空格

折后效果:

foldedExample.c
1
2
3
#include <stdio.h>
int main()
+--  4 : {------------------------------------------------------------

打开折叠z+o

打开文件中所有折叠z+O

删除一个折叠z+e

删除文件中所折叠z+e

折叠不会被写入到文件里,如果使用cat less查看代码,代码将以无任何折叠的方式显示。

A folder is just a tag which tells vim to display something as a folder. So it is also possible to write a file with folders. To mark the start of a folder just use for example in a comment of a source file) and to mark the end of the folder.

ForMore
Awesome

STL中最常用的函数之一,排序的神器。

sort

function sort.cpp
1
2
3
4
5
6
<algorithm>
template <class RandomAccessIterator>
  void sort ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
  void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );

function

Sort elements in range Sorts the elements in the range first,last) into ascending order.

The elements are compared using operator< for the first version, and comp for the second.

Elements that would compare equal to each other are not guaranteed to keep their original relative order.

Parameters

first, last Random-Access iterators to the initial and final positions of the sequence to be sorted. The range used is first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last. comp Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.

Return value

none

Example

example.cpp
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
// sort algorithm example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool myfunction (int i,int j) { return (i<j); }

struct myclass {
  bool operator() (int i,int j) { return (i<j);}
} myobject;

int main () {
  int myints[] = {32,71,12,45,26,80,53,33};
  vector<int> myvector (myints, myints+8);               // 32 71 12 45 26 80 53 33
  vector<int>::iterator it;

  // using default comparison (operator <):
  sort (myvector.begin(), myvector.begin()+4);           //(12 32 45 71)26 80 53 33

  // using function as comp
  sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)

  // using object as comp
  sort (myvector.begin(), myvector.end(), myobject);     //(12 26 32 33 45 53 71 80)

  // print out content:
  cout << "myvector contains:";
  for (it=myvector.begin(); it!=myvector.end(); ++it)
    cout << " " << *it;

  cout << endl;

  return 0;
}

Output:

myvector contains: 12 26 32 33 45 53 71 80

Complexity

Approximately NlogN comparisons on average (where N is last-first). In the worst case, up to N2, depending on specific sorting algorithm used by library implementation.

做TC练习的时候,学习高手的代码,看到了这个神器。用于生成不重复的且不小于当前排列的全排列。

next_permutation

function fun.cpp
1
2
3
4
5
6
7
 template <class BidirectionalIterator>
  bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last );

template <class BidirectionalIterator, class Compare>
  bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last, Compare comp);

Transform range to next permutation

Rearranges the elements in the range first, last) into the lexicographically next greater permutation of elements. The comparisons of individual elements are performed using either operator< for the first version, or comp for the second.

A permutation is each one of the N! possible arrangements the elements can take (where N is the number of elements in the range). Different permutations can be ordered according on how they compare lexicographicaly to each other; The first such-sorted possible permutation (the one that would compare lexicographically smaller to all other permutations) is the one which has all its elements sorted in ascending order, and the largest has all its elements sorted in descending order.

If the function can determine the next higher permutation, it rearranges the elements as such and returns true. If that was not possible (because it is already at the largest), it rearranges the elements according to the first permutation (sorted in ascending order) and returns false.

Parameters

first, last Bidirectional iterators to the initial and final positions of the sequence. The range used is first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last. comp Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument is to be considered less than the second argument.

Return value

true if the function could rearrange the object as a lexicographicaly greater permutation. Otherwise, the function returns false to indicate that the arrangement is not greater than the previous, but the lowest possible (sorted in ascending order).

Example

next_permutation tset.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <algorithm>
using namespace std;

int main () {
  int myints[] = {1,2,3};

  cout << "The 3! possible permutations with 3 elements:\n";

  sort (myints,myints+3);

  do {
    cout << myints[0] << " " << myints[1] << " " << myints[2] << endl;
  } while ( next_permutation (myints,myints+3) );

  return 0;
}

Output:

The 3! possible permutations with 3 elements:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

注意

当输出{1, 1, 1}的全排列时只输出一组“1 1 1”;

上升全排列

int myints[] = {1,2,3}; 输出为:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

int myints[] = {3,2,1}; 输出为:
3 2 1

int myints[] = {2,3,1}; 输出为:
2 3 1
3 1 2
3 2 1

所以想得到给定数组元素的全排列,首先要sort为单调上升序列。

Complexity

At most, performs one half as many swaps as the number of elements in the range.

脑袋里有一个模糊的“思维导图”的东东,当然之前没有“思维导图”的概念,最近浏览TL时,偶得一利器Graphviz & DOT language. 恰是吾之所求。下面是WIKI & 官网的简介。

Graphviz:

REXML could not parse this XML/HTML: 
<blockquote><p>AT&T Labs Tools for viewing and interacting with graph diagrams.<br />Graph visualization is a way of representing structural information as diagrams of abstract graphs and networks. Automatic graph drawing has many important applications in software engineering, database and web design, networking, and in visual interfaces for many other domains. Graphviz is open source graph visualization software. It has several main graph layout programs.</p></blockquote>

DOT

DOT is a plain text graph description language. It is a simple way of describing graphs that both humans and computer programs can use. DOT graphs are typically files that end with the .gv (or .dot) extension. The .gv extension is preferred, as the .dot file extension is used by Microsoft Office 2003.

简而言之,我们用dot语言来表达我们的思想,将流程、关系利用Graphviz“翻译”图形化。Graphviz主要支持两种关系图:

* 有向 * 无向

无向图:

这是DOT最简单的应用。只需用“- -”来表示节点间有关系的。例子如下:

Undirected graph test2 file
1
2
3
4
graph graphName{
	a -- b -- c;
	b -- d;
}

有向图:

同样是DOT简单的应用。只需用“- >”来表示节点间有关系的。例子如下:

Directed graph test2 file
1
2
3
4
digraph graphName{
	a -> b -> c;
	b -> d;
}

修改样式:

在花括号内添加边和节点的定义

1
2
node [shape="record"];
edge [style="dashed"];

五一已过。任务没有完成。好久没有静下来想点什么、做点什么了。但时间还是一样的过。看一下自己的备忘表,已经快一周没有记录与勾画了。想起一句话“宁要一个结束,也不要千万个开始”。“善始者实繁,克终者盖寡”,总是习惯于做那个分母。

好久没有失眠了,好久没有清醒的过活。好像只有稀里糊涂的安逸才能在夜里顺其自然的入眠。细想一下最近过的还好。充满幸福感的五一。

当我呆在一个小空间里太久,结果产生错觉,以为自己掌握了整个人生。触摸世界成了坐井观天,甚至根本不会去想世界的五彩。越来越发觉世界真的好大好大,琦丽无比,就如梦中的情人,朦胧的美感,唯有用心去细细体味。越来越觉得人可以活得很丰富很丰富,有时,我们可以像一只目不转睛般伏猎几日的非洲狮;有时,我们可以像一只冲破牢笼回归自然的幼鸟。

长大了么?开始觉得人要学会适应孤独,“一个人要活得像一支队伍”。 还记得那“的叔”,满脸微笑兴奋的指着我说:“这么小耍啥子朋友”。一边指给我们乘车的方向,而后又对我们说“有没有十八岁?”。我笑着想小鸡啄米般点头…

记录一下短期到计划,充实的暑假前的生活,啃书,听歌,给亲人朋友问候,生活再规律一点点…

今天磨蹭了一天,也还是没有结果,现在有了源码。有了PARTS。但是编译是终会有这样的错误提示:
1
2
ucos_ii.c:24:21: 致命错误: ucos_ii.h:没有那个文件或目录
编译中断。
不清楚是什么问题,明明有那个文件,就是提示不存在。

每次文件解压都要去翻鸟哥。今天总结下: 文件后缀名有:x.Z \ x.gz2 x.tar x.tar.gz x.gz.值得一提的是查看压缩文件不一定需要解压文件。