如何在不失去功能的情况下将2 for循环更改为1 while循环 [英] How do I change 2 for loops into 1 while loop without loosing funtionality

问题描述

您好，



我需要更改以下代码（其中包含3个FOR循环）

到1'WEILE'和' 2 FOR循环'。我的代码（位于你尝试过的东西）有效，但不正确。 ¬

我在某些边缘得到了垃圾。我把问题隔离到了i和k过程。

请帮忙。



提前致谢。



原始代码段

Hello,

I need to change the following code (which contains 3 FOR Loops)
to 1 'WHILE' and '2 FOR loops'. My code, (located in "what have you tried") works but not correct. ¬
I'm getting garbage in some of the edges. I have isolated the problem to the i and k process.
Please help.

Thanks in advance.

Original Code Segment

mstv[source] = true;
edgeWeights[source] = 0;

for (int i = 0; i < gSize - 1; i++)
{
	minWeight = DBL_MAX;

	for (int j = 0; j < gSize; j++)
		if (mstv[j])
		for (int k = 0; k < gSize; k++)
		if (!mstv[k] && weights[j][k] < minWeight)
		{
			endVertex = k;
			startVertex = j;
			minWeight = weights[j][k];
			cout << " endVertex K " << endVertex << endl;
			cout << " start J " << startVertex << endl;
			cout << " minweight " << minWeight << endl;
		}
	
		mstv[endVertex] = true;
		edges[endVertex] = startVertex;
		edgeWeights[endVertex] = minWeight;
	} //end for
} //end minimalSpanning

问题定义



写一个新函数（Prim2）的定义来实现这个算法



输入：连接加权图G =（V，E）的N个顶点，编号为0,1,2 ,,,, n-1;

以顶点s开头，带有权重W的矩阵。

输出：最小生成树。

The Problem Definition

Write a definition of the new function (Prim2) to implement this algorithm

Input: A connected weighted graph G = (V, E) of N vertices, numbered 0, 1, 2,,,, n-1;
starting with vertex s, with a weight matrix of W.
Output: The minimal spanning tree.

Prim2 (G, W, n, s)
Let T = (V, E), where E = 0
for ( j = 0; j < n; j ++) to n
{
	edgeWeights [ j ] = W(s, j);
	edges [ j ] = s;
	visited [ s ] = false;
}
edgeWeights [ s ] = 0;
visited [ s ] = true
while (not all nodes are visited)
{
	Choose the node that is not visited and has the smallest weight, and call it k.
	visited [ k ] = true;
	E = E U { ( k, edges [ k ] ) }
	V = V U { k }
	for each node j that is not visited
	if (W ( k, j ) < edgeWeights [ j ])
	{
		edgeWeights [ j ] = W ( k, j );
		edges[ j ] = k;
	}
	return T;

< br $> b $ b

我的代码段

My Code Segment

visited[source] = true; edgeWeights[source] = 0; int i = 0, int k = 0 // choose node that's not visited and has the smallest weight

while (! visited[i] && (k < gSize)) { // nodes have not been visited
	visited[k] = true; k++;

	for (int j = 0; j < gSize; j++) // for each node 'j' that is not visited
		if (weights[k][j] < 	edgeWeights[j]) {
			(edgeWeights[j] = weights[k][j]);
			edges[j] = k;
			cout << " Edge Weight " <<
			edgeWeights[j] << endl; cout << " Edges K " << edges[j] << endl;
	
		} } // end while } // end prim2 Function

推荐答案

想象一下 for loop - cppreference.com [ ^ ]正在执行以及何时执行部件：

Just imagine what a for loop - cppreference.com[^] is doing and when the parts are executed:

for (init_statement; condition; iteration_expression)

执行为

is executed as

init_statement;
while (condition)
{
    // Body
    iteration_expression;
}

因此在执行正文后执行 iteration_expression 。但是在你的代码中，它是在错误的地方执行的，你使用的是两个数组索引，其中 i 永远不再使用（已更改）：

So the iteration_expression is executed after the body has been executed. But in your code it is executed at the wrong place and you are using two array indexes where i is never used again (changed):

int i = 0;
int k = 0;
while (! visited[i] && (k < gSize)) 
{ 
    visited[k] = true; 
    // This is wrong here!
    // Move it below the body block.
    //k++;

    // Body

    // Insert iteration_expression(s) here.
    k++;
    // Incrementing i is absent in your code.
    i++;
}

在您的情况下，您可以省略一个迭代变量。我没有检查过你的算法但看起来你的 visit 数组的使用在这里是没用的。也许你想做这样的事情（但是又一次：我不知道这是否会破坏算法）：

In your case you may omit one iteration variable. I have not checked your algorithm but it looks like the usage of your visited array is useless here. Maybe you want to do something like this (but again: I don't know if this breaks the algorithm):

memset(visited, 0, sizeof(visited));
int k = 0;
while (k < gSize)
{
    if (!visited[k])
    {
        for (int j = 0; j < gSize; j++)
        {
            if (weights[k][j] < edgeWeights[j]) 
            {          
                // Calculation
                visited[j] = true;  
            }
    }
    k++;
}

这篇关于如何在不失去功能的情况下将2 for循环更改为1 while循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！