分解向量的算法 [英] Algorithm to break up a vector

问题描述

大家好：


我不确定这是否是提出这个问题的合适地方，但是我无法找到
一个更合适的群体。这更像是一个关于用C语言实现的算法的理论问题，不一定是C语言问题。


我我试图将一个向量分解为任意数量的子向量，

的大小等于（或接近相等）。我的问题发生在

时，向量不能被子向量的数量整除（即，

向量长度：45，子向量的数量：7）


如果我基于（int）（vectorsize / numsubvectors）分解向量，而不是

将包含所有原始向量数据。如果我基于ceil（vectorsize / numsubvectors）分解

向量，将传递向量

的结尾，从而导致内存违规。


上面例子的显而易见的解决方案是有3个子向量

大小为7，还有4个子向量大小为6，但我很难思考

一种实现此方法的方法，用于任意向量大小和

子向量的数量。我知道mod（％）运算符可能是必需的，我知道

对于上面的例子，我需要的算法会产生：


子向量1：尺寸6

子矢量2：尺寸7

子矢量3：尺寸6

子矢量4：尺寸7

子矢量5：尺寸6

子矢量6：尺寸7

子矢量7：尺寸6


任何人都有任何想法？


谢谢。

解决方案

没有这样的Luck写道：

大家好：

我不确定这是否是提出这个问题的合适地方，但是我找不到一个更合适的群体。这更像是一个关于用C实现的算法的理论问题，不一定是C语言问题。


如果您给我们使用C代码，那么我们将指出

可能的算法缺点。

请求一个C算法在这里不是主题。

comp.programming可能是一个很好的起点，要求

算法。然后你可以实现它 - 如果你因为你的程序没有按预期运行而导致
问题，那么你可以隔离一个最小的运行程序展示

这些问题我们会帮助你。


我试图将一个向量分解为任意数量的子向量，
相等（或接近）等于）尽可能大小。我的问题发生在
向量不能被子向量的数量整除时（即，矢量长度：45，子向量的数量：7）

如果我分手了矢量基于（int）（vectorsize / numsubvectors），而不是
将包括所有原始矢量数据。如果我基于ceil（vectorsize / numsubvectors）分解
向量，将传递向量的结尾
，从而导致内存违规。

显而易见的解决方案上面的例子是有3个大小为7的子向量，以及4个大小为6的子向量，但是我很难想到为任意向量大小和数量实现这个的方法。的子向量。我知道mod（％）运算符可能是必需的，我知道
对于上面的例子我将需要的算法：

子向量1：大小6
子向量2 ：尺寸7
子矢量3：尺寸6
子矢量4：尺寸7
子矢量5：尺寸6
子矢量6：尺寸7
子矢量7：尺寸6

任何人有什么想法？

是的。这听起来像是一个愚蠢的家庭作业问题。更自然

将给出子向量的最大长度并且用于

7 | 7 | 7 | 6 | 6 | 6 | 6而不是6 | 7 | 6 | 7 | 6 | 7 | 6。


提示：

45/7 = 6

45％7 = 3

干杯

Michael

-

电子邮件：我的是gmx dot de address。 />

No Such Luck写道：

大家好：

我不确定这是不是问这个问题的合适地方，但是我找不到更合适的小组。这更像是一个关于用C语言实现的算法的理论问题，不一定是C语言问题。

我试图将一个向量分解为一个任意的子向量的数量，
大小相等（或接近相等）。我的问题发生在
向量不能被子向量的数量整除时（即，矢量长度：45，子向量的数量：7）

如果我分手了矢量基于（int）（vectorsize / numsubvectors），而不是
将包括所有原始矢量数据。如果我基于ceil（vectorsize / numsubvectors）分解
向量，将传递向量的结尾
，从而导致内存违规。

显而易见的解决方案上面的例子是有3个大小为7的子向量，以及4个大小为6的子向量，但是我很难想到为任意向量大小和数量实现这个的方法。的子向量。我知道mod（％）运算符可能是必需的，我知道
对于上面的例子我将需要的算法：

子向量1：大小6
子向量2 ：尺寸7
子矢量3：尺寸6
子矢量4：尺寸7
子矢量5：尺寸6
子矢量6：尺寸7
子矢量7：尺寸6

一个简单的方法是进行（伪代码）：


int vecsize =原始向量的长度;

int subcount =所需子向量的数量;

int subsizes [subcount];

for（; subcount> 0; --subcount）{

subsizes [subcount-1] =

（2 * vecsize + subcount）/（2 * subcount）;

vecsize - = subsizes [subcount-1 ];

}


（中间的混乱仅仅是vecsize / subcount，

四舍五入。你可以使用普通的整数除法或

aceiling而不影响方法的有效性，

但你会得到一个di长短的传送模式

子向量。）


这种方法将平均子矢量长度平衡为

尽可能。它的主要优点是它很容易理解为什么它有效，因而很难出错。


< off-topic>


它也是一个分而治之的

解决方案的一个说明性例子* *不要求求递归实现。


< / off-topic>


-
Er ********* @ sun.com

Eric Sosman < ER ********* @ sun.com>在消息中写道

news：cp ********** @ news1brm.Central.Sun.COM ...

No Such Luck写道：

我不确定这是否是提出这个问题的合适场所，但是我找不到更合适的团体。这更像是一个关于用C语言实现的算法的理论问题，不一定是C语言问题。

我试图将一个向量分解为一个任意的子向量的数量，
大小相等（或接近相等）。我的问题发生在
向量不能被子向量的数量整除时（即，矢量长度：45，子向量的数量：7）

如果我分手了矢量基于（int）（vectorsize / numsubvectors），而不是
将包括所有原始矢量数据。如果我基于ceil（vectorsize / numsubvectors）分解
向量，将传递向量的结尾
，从而导致内存违规。

显而易见的解决方案上面的例子是有3个大小为7的子向量，以及4个大小为6的子向量，但是我很难想到为任意向量大小和数量实现这个的方法。的子向量。我知道mod（％）运算符可能是必需的，我知道
对于上面的例子我将需要的算法：

子向量1：大小6
子向量2 ：尺寸7
子矢量3：尺寸6
子矢量4：尺寸7
子矢量5：尺寸6
子矢量6：尺寸7
子矢量7：尺寸6

一个简单的方法是进行（伪代码）：

int vecsize =原始向量的长度;
int subcount =所需子向量的数量;
int subsizes [subcount];
for（; subcount> 0; --subcount）{
subsizes [subcount-1] =
（2 * vecsize + subcount）/ （2 * subount）;
vecsize - = subsizes [subcount-1];


（中间的混乱只是vecsize / subcount，
圆形。你可以使用普通的整数除法或
一个天花板而不影响方法的有效性，但是你会得到一个不同的长短模式 sub-vecto rs。）

此方法将尽可能均匀地平衡子矢量长度。它的主要优点是它很容易理解为什么它有效，因而很难出错。

< off-topic>

它这也是一个分而治之的解决方案的说明性例子* *不要求递归实现。

< / off-topic>

谢谢，Eric。我将在明天给这个实施一个旋转。分裂和

征服技术从未发生过。我以为我必须确定开头所有子向量的大小......

Hi All:

I''m not sure if this is the right place to ask this question, but I
couldn''t find a more appropriate group. This is more of a theory
question regarding an algorithm implemented in C, not necessarily a C
language question.

I''m trying to break up a vector into an arbitrary number of subvectors,
equal (or as near to equal) in size as possible. My problem occurs when
the vector is not evenly divisible by the number of subvectors (i.e.,
vector length: 45, number of subvectors: 7)

If I break up the vector based on (int)(vectorsize/numsubvectors), not
all of the original vector data will be included. If I break up the
vector based on ceil(vectorsize/numsubvectors), the end of the vector
will be passed, resulting in a memory violation.

The obvious solution to the above example be to have 3 subvectors of
size 7, and 4 subvectors of size 6, but I''m having a hard time thinking
of a way to implement this for an arbitrary vector size and number of
subvectors. I know the mod(%) operator is probably required, and I know
for the above example that the algorithm I need will result:

Subvector 1: Size 6
Subvector 2: Size 7
Subvector 3: Size 6
Subvector 4: Size 7
Subvector 5: Size 6
Subvector 6: Size 7
Subvector 7: Size 6

Anyone have any ideas?

Thanks.

解决方案

No Such Luck wrote:

Hi All:

I''m not sure if this is the right place to ask this question, but I
couldn''t find a more appropriate group. This is more of a theory
question regarding an algorithm implemented in C, not necessarily a C
language question.
If you give us C code to work with, then we will point out
possible algorithmic shortcomings.
A request for a C algorithm is not topical here.
comp.programming might be a good starting point to ask for
an algorithm. Then you can implement it -- and if you have
problems because your program does not run as intended,
then you can isolate a minimal running program exhibiting
these problems and we will help you.

I''m trying to break up a vector into an arbitrary number of subvectors,
equal (or as near to equal) in size as possible. My problem occurs when
the vector is not evenly divisible by the number of subvectors (i.e.,
vector length: 45, number of subvectors: 7)

If I break up the vector based on (int)(vectorsize/numsubvectors), not
all of the original vector data will be included. If I break up the
vector based on ceil(vectorsize/numsubvectors), the end of the vector
will be passed, resulting in a memory violation.

The obvious solution to the above example be to have 3 subvectors of
size 7, and 4 subvectors of size 6, but I''m having a hard time thinking
of a way to implement this for an arbitrary vector size and number of
subvectors. I know the mod(%) operator is probably required, and I know
for the above example that the algorithm I need will result:

Subvector 1: Size 6
Subvector 2: Size 7
Subvector 3: Size 6
Subvector 4: Size 7
Subvector 5: Size 6
Subvector 6: Size 7
Subvector 7: Size 6

Anyone have any ideas?

Yes. This sounds like an idiotic homework question. More natural
would be to give the maximum length of subvectors and to go for
7|7|7|6|6|6|6 instead of 6|7|6|7|6|7|6.

Hints:
45/7 = 6
45%7 = 3
Cheers
Michael
--
E-Mail: Mine is a gmx dot de address.

No Such Luck wrote:

Hi All:

I''m not sure if this is the right place to ask this question, but I
couldn''t find a more appropriate group. This is more of a theory
question regarding an algorithm implemented in C, not necessarily a C
language question.

I''m trying to break up a vector into an arbitrary number of subvectors,
equal (or as near to equal) in size as possible. My problem occurs when
the vector is not evenly divisible by the number of subvectors (i.e.,
vector length: 45, number of subvectors: 7)

If I break up the vector based on (int)(vectorsize/numsubvectors), not
all of the original vector data will be included. If I break up the
vector based on ceil(vectorsize/numsubvectors), the end of the vector
will be passed, resulting in a memory violation.

The obvious solution to the above example be to have 3 subvectors of
size 7, and 4 subvectors of size 6, but I''m having a hard time thinking
of a way to implement this for an arbitrary vector size and number of
subvectors. I know the mod(%) operator is probably required, and I know
for the above example that the algorithm I need will result:

Subvector 1: Size 6
Subvector 2: Size 7
Subvector 3: Size 6
Subvector 4: Size 7
Subvector 5: Size 6
Subvector 6: Size 7
Subvector 7: Size 6

An easy way to proceed is (pseudocode):

int vecsize = length of original vector;
int subcount = number of sub-vectors desired;
int subsizes[subcount];
for ( ; subcount > 0; --subcount) {
subsizes[subcount-1] =
(2 * vecsize + subcount) / (2 * subcount);
vecsize -= subsizes[subcount-1];
}

(That mess in the middle is merely "vecsize / subcount,
rounded." You could use an ordinary integer division or
a "ceiling" without affecting the validity of the method,
but you''d get a different pattern of long and short
sub-vectors.)

This method will balance the sub-vector lengths as
evenly as is possible. Its principal virtue is that it''s
easy to see why it works, and hence hard to get wrong.

<off-topic>

It''s also an illustrative example of a divide-and-conquer
solution that *doesn''t* beg for a recursive implementation.

</off-topic>

--
Er*********@sun.com

"Eric Sosman" <er*********@sun.com> wrote in message
news:cp**********@news1brm.Central.Sun.COM...

No Such Luck wrote:

Hi All:

I''m not sure if this is the right place to ask this question, but I
couldn''t find a more appropriate group. This is more of a theory
question regarding an algorithm implemented in C, not necessarily a C
language question.

I''m trying to break up a vector into an arbitrary number of subvectors,
equal (or as near to equal) in size as possible. My problem occurs when
the vector is not evenly divisible by the number of subvectors (i.e.,
vector length: 45, number of subvectors: 7)

If I break up the vector based on (int)(vectorsize/numsubvectors), not
all of the original vector data will be included. If I break up the
vector based on ceil(vectorsize/numsubvectors), the end of the vector
will be passed, resulting in a memory violation.

The obvious solution to the above example be to have 3 subvectors of
size 7, and 4 subvectors of size 6, but I''m having a hard time thinking
of a way to implement this for an arbitrary vector size and number of
subvectors. I know the mod(%) operator is probably required, and I know
for the above example that the algorithm I need will result:

Subvector 1: Size 6
Subvector 2: Size 7
Subvector 3: Size 6
Subvector 4: Size 7
Subvector 5: Size 6
Subvector 6: Size 7
Subvector 7: Size 6

An easy way to proceed is (pseudocode):

int vecsize = length of original vector;
int subcount = number of sub-vectors desired;
int subsizes[subcount];
for ( ; subcount > 0; --subcount) {
subsizes[subcount-1] =
(2 * vecsize + subcount) / (2 * subcount);
vecsize -= subsizes[subcount-1];
}

(That mess in the middle is merely "vecsize / subcount,
rounded." You could use an ordinary integer division or
a "ceiling" without affecting the validity of the method,
but you''d get a different pattern of long and short
sub-vectors.)

This method will balance the sub-vector lengths as
evenly as is possible. Its principal virtue is that it''s
easy to see why it works, and hence hard to get wrong.

<off-topic>

It''s also an illustrative example of a divide-and-conquer
solution that *doesn''t* beg for a recursive implementation.

</off-topic>

Thanks, Eric. I will give this implementation a whirl tomorrow. A divide and
conquer technique never occurred to me. I thought I would have to determine
the size of all the subvectors in the outset...

这篇关于分解向量的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！