浦西 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

浦西

浦西# Joke - 肚皮舞运动

k*p2011-02-13 08:02

1 楼

我无耻，我少写了个条件
要保证B数组也是升序排列的。
新题：
one integer array A with ascending order, for example 1 ,2 ,3,4, please
generate another array B with any sum of any 3
different numbers picked from the A with ascending order, for example for 1,2,3,4, the result is
(1+2+3),(1＋2＋4),(1＋3＋4),(2＋3＋4）“
原来的题：
”
one integer array A with ascending order, for example 1 ,2 ,3,4, please
generate another array B with any 3
different numbers picked from the A, for example for 1,2,3,4, the result is
(1+2+3),(1,2,4),(1,3,4),(2,3,4）“
谢谢。

b*g2011-02-13 08:02

2 楼

收到银行来信，内容是 W-8BEN Foreign Status of business owner
说我foreign status expires
要我填表格，回信。
我就填了就回信？

v*82011-02-13 08:02

3 楼

【以下文字转载自 LoveNLust 讨论区】
发信人: vt88 (abc), 信区: LoveNLust
标题: 浦西
发信站: BBS 未名空间站 (Sun Feb 13 00:17:56 2011, 美东)
lovepussy
pussypussy
yeahpussy
lickpussy
有什么区别？

k*p2011-02-13 08:02

4 楼

另外，如果扩展到 k位数呢？

l*g2011-02-13 08:02

5 楼

还是foreign status就回咯
这个表格三年有效期

【在 b****g 的大作中提到】

: 收到银行来信，内容是 W-8BEN Foreign Status of business owner
: 说我foreign status expires
: 要我填表格，回信。
: 我就填了就回信？

v*82011-02-13 08:02

6 楼

到底哪个算淫荡ID？

【在 v**8 的大作中提到】

: 【以下文字转载自 LoveNLust 讨论区】
: 发信人: vt88 (abc), 信区: LoveNLust
: 标题: 浦西
: 发信站: BBS 未名空间站 (Sun Feb 13 00:17:56 2011, 美东)
: lovepussy
: pussypussy
: yeahpussy
: lickpussy
: 有什么区别？

g*k2011-02-13 08:02

7 楼

isn't this just a recursive function with prototype like
f(int A[], int lengthA, int B[], int lengthB, int cur_pos)
when you choose index for B[cur_pos], you choose one from
B[cur_pos - 1]+1 to lengthA.

is

【在 k*******p 的大作中提到】

: 另外，如果扩展到 k位数呢？

H*e2011-02-13 08:02

8 楼

大胆推测一下。
这里面凡是文情帮的人的马甲就不是淫荡的，而是艺术的，是在文学艺术上合情合理但
不一定合法的充满情趣和爱心，耐心的。
。

【在 v**8 的大作中提到】

: 到底哪个算淫荡ID？

k*p2011-02-13 08:02

9 楼

不太明白你的解法，你能举例子吗。

c*e2011-02-13 08:02

10 楼

恩，都算。都应该杀档。

【在 H*******e 的大作中提到】

: 大胆推测一下。
: 这里面凡是文情帮的人的马甲就不是淫荡的，而是艺术的，是在文学艺术上合情合理但
: 不一定合法的充满情趣和爱心，耐心的。
: 。

g*y2011-02-13 08:02

11 楼

run(new int[]{1, 2, 3, 4}, 3, 0, "");
public void run(int[] a, int n, int p, String result) {
if (n == 0) {
System.out.println(result);
return;
}

for (int i=p; i<=a.length-n; i++) {
run(a, n-1, i+1, result + " " + a[i]);
}
}

x*o2011-02-13 08:02

12 楼

here is the C++ code:
#include
#include
#include
using namespace std;
void print_vector(const vector &v){
vector::const_iterator iter=v.begin();
while(iter!=v.end()){
cout<++iter;
}
cout<}
void subset(vector v, vector sub, int size,set > &s){
if(sub.size()==size){
sort(sub.begin(),sub.end());
s.insert(sub);
return;
}
vector::iterator iter=v.begin();
size_t l=v.size();
for(int i=0;ivector temp(v);
vector subs(sub);
temp.erase(temp.begin()+i);
subs.push_back(v[i]);
subset(temp,subs,size,s);
}
}
int main(){
int a[]={1,2,3,4};
vector v(a,a+4);
vector sub;
set > s;
subset(v,sub,3,s);
set >::const_iterator iter=s.begin();
while(iter!=s.end()){
print_vector(*iter);
++iter;
}
return 0;
}

k*p2011-02-13 08:02

13 楼

题目我写错了，已经修改。这个递归写的很neat 赞一个。

【在 g**********y 的大作中提到】

: run(new int[]{1, 2, 3, 4}, 3, 0, "");
: public void run(int[] a, int n, int p, String result) {
: if (n == 0) {
: System.out.println(result);
: return;
: }
:
: for (int i=p; i<=a.length-n; i++) {
: run(a, n-1, i+1, result + " " + a[i]);
: }

f*42011-02-13 08:02

14 楼

就是 n choose k的combination啊；把打印替换成sum->array
只要从最小数开始，就能符合结果递增

k*p2011-02-13 08:02

15 楼

这样的话，可以全部打出来，但你保证不了排序，比如 a数组是 {1, 8, 9, 10,26} 从
最小数一直打，结果是：
1 8
1 9
1 10
1 26
8 9（错误）
8 10
8 26
9 10
9 26
10 26

f*42011-02-13 08:02

16 楼

还有别的要求没有？
没有的话就再搞个BST，算出来的sum insert进去，最后中续遍历输出
要是在combine过程当中搞的话，要想想

h*n2011-02-13 08:02

17 楼

8,9 怎么错了啊？b的排序不是这么拍
的么？

import copy
def select(array, start, depth):
if depth==0:
print array
else:
for i in range(start, len(array)):
arrayCopy = copy.deepcopy(array)
del arrayCopy[i]
select(arrayCopy, i, depth-1)
def select2(array, string, start, depth):
if depth==0:
print string
else:
for i in range(start, len(array)):
string.append(array[i])
select2(array, string, i+1, depth-1)
del string[len(string)-1]
#select([1,2,3,4,5,6], 0, 2) #倒着打印
select2([1,2,3,4,5,6], [], 0, 3) #正着打印

【在 k*******p 的大作中提到】

: 这样的话，可以全部打出来，但你保证不了排序，比如 a数组是 {1, 8, 9, 10,26} 从
: 最小数一直打，结果是：
: 1 8
: 1 9
: 1 10
: 1 26
: 8 9（错误）
: 8 10
: 8 26
: 9 10

s*y2011-02-13 08:02

18 楼

co-ask.

【在 h*********n 的大作中提到】

: 8,9 怎么错了啊？b的排序不是这么拍
: 的么？
:
: import copy
: def select(array, start, depth):
: if depth==0:
: print array
: else:
: for i in range(start, len(array)):
: arrayCopy = copy.deepcopy(array)

f*42011-02-13 08:02

19 楼

那个是回我的帖子

d*l2011-02-13 08:02

20 楼

题目的意思相当于有序打印集合A所有大小为3的子集，代码如下：
void run(int a[], int n, int m, vector &subset)
{
if(n < m) return ;
if(m == 0) {
for(int i = 0; i < subset.size(); i++)
cout << subset[i] << " ";
cout << endl;
return ;
}
subset.push_back(a[0]);
run(a+1, n-1, m-1, subset);
vector::iterator it;
subset.erase(subset.begin() + subset.size() - 1);
run(a+1, n-1, m, subset);
}
int a[10] = {1,8,9,10,26};
int main() {
vector v(0);
run(a, 5, 2, v);
return 0;
}
初始传入的参数是数组地址a，数组大小n，要打印的子集的大小m以及一个空的vector
。程序将按顺序打印所有子集。其实就是递归的先打印包含当前数，剩下集合所有大小
为m-1的子集，和不包含当前数，剩下集合大小为m的子集。

g*k2011-02-13 08:02

21 楼

Why you people like to decrement m instead of incrementing m?
By increment, you can get rid of push_back and erase, if you reserve size m
for subset.
Thus you can access subset[m] each time and don't need to erase elements.

题目的意思相当于有序打印集合A所有大小为3的子集，代码如下：
void run(int a[], int n, int m, vector &subset)
{
if(n < m) return ;
if(m == 0) {
for(int i = 0; i < subset.size(); i++)
cout << subset[i] << " ";
cout << endl;
return ;
}
subset.push_back(a[0]);
run(a+1, n-1, m-1, subset);
vector::iterator it;
subset.erase(subset.begin() + subset.size() - 1);
run(a+1, n-1, m, subset);
}
int a[10] = {1,8,9,10,26};
int main() {
vector v(0);
run(a, 5, 2, v);
return 0;
}
初始传入的参数是数组地址a，数组大小n，要打印的子集的大小m以及一个空的vector
。程序将按顺序打印所有子集。其实就是递归的先打印包含当前数，剩下集合所有大小
为m-1的子集，和不包含当前数，剩下集合大小为m的子集。

【在 d*******l 的大作中提到】

: 题目的意思相当于有序打印集合A所有大小为3的子集，代码如下：
: void run(int a[], int n, int m, vector &subset)
: {
: if(n < m) return ;
: if(m == 0) {
: for(int i = 0; i < subset.size(); i++)
: cout << subset[i] << " ";
: cout << endl;
: return ;
: }

k*p2011-02-13 08:02

22 楼

1＋26 比 8＋9 大了，b数组每个数是三个a数组数字的和。b也要保持升序。

【在 h*********n 的大作中提到】

d*l2011-02-13 08:02

23 楼

我想这是因为递减m的话就可以少加个参数，因为直接判断是否为0即可。这题大家都没
有优先考虑效率的问题，似乎都是想尽量写简洁，真要从效率出发，肯定不能用vector
，直接用个数组就行，这时需要多加个参数标记当前的位置，数组的push和pop体现在
位置的移动，就不需要额外开销了。

m

【在 g*****k 的大作中提到】

: Why you people like to decrement m instead of incrementing m?
: By increment, you can get rid of push_back and erase, if you reserve size m
: for subset.
: Thus you can access subset[m] each time and don't need to erase elements.
:
: 题目的意思相当于有序打印集合A所有大小为3的子集，代码如下：
: void run(int a[], int n, int m, vector &subset)
: {
: if(n < m) return ;
: if(m == 0) {

g*k2011-02-13 08:02

24 楼

哦，原来是为了简洁啊。明白了

vector

【在 d*******l 的大作中提到】

: 我想这是因为递减m的话就可以少加个参数，因为直接判断是否为0即可。这题大家都没
: 有优先考虑效率的问题，似乎都是想尽量写简洁，真要从效率出发，肯定不能用vector
: ，直接用个数组就行，这时需要多加个参数标记当前的位置，数组的push和pop体现在
: 位置的移动，就不需要额外开销了。
:
: m