删除递归[英] Removing recursion

问题描述

大家好.

我有一个 C++ 程序,可以计算网格中的 YOYOs
Y 和 O.比如这个

哟哟哟哟哟
哦哦哦哦哦
哟哟哟哟哟
哦哦哦哦哦
O Y Y O Y O

应该有 406 YOYO's 在里面.YOYO's 一个上、下、右、左带
弯曲和对角线.

我的程序运行良好,但它使用递归,我想工作
迭代.

这是程序:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

常量 int max_points = 10;
extern int maxy, maxx;

结构点{
整数;
整数 x;
点 () { y = x = 0;}
点 (int ey, int ex) { y = ey;x = 前;}
无效集(int ey,int ex){ y = ey;x = 前;}
布尔入站(){
if (y < 0 || y >= maxy) { return false;}
if (x < 0 || x >= maxx) { return false;}
返回真;
}
char * as_string() {
字符 * 温度 = 新字符 [10];
sprintf(temp, "(%d,%d)", y, x);
返回温度;
}
void print() { printf("%s", as_string());}
};

结构 Pointgrp {
国际化;
点点数[max_points];
无效打印(){
for (int pos = 0; pos < len; ++pos) {
点[pos].print();
}
放("");
}
};

结构见{
字符数据[1000];
看到(){清除();}
void clear() { memset(data,0,sizeof(data));}
字符&pos(int y, int x) {
返回数据[(y * maxx) + x];
}
void init(const Pointgrp & pts) {
for (int pix = 0; pix < pts.len; ++pix) {
常量点&mypt = pts.points[pix];
pos(mypt.y, mypt.x) = 1;
}
}
字符&posPoint(const Point & pt) {
pos(pt.y, pt.x);
}
};

char * yoyo1 [] = {
"年年,
"悠悠球,
"OYYOYYO",
"OYYYO",
"年年,
"",
};

char * yoyo2 [] = {
"哟",
〝OY〞,
"",
};

char * yoyo3 [] = {
《悠悠悠》,
《悠悠悠》,
"YOYYOY",
"OYOOYO",
"OYYOYO",
"",
};

char ** 网格 = yoyo1;
int maxx = 7;
int maxy = 5;

const char * search_for = "YOYO";
int search_len = 4;
int wordcount = 0;

//------------------------------

字符&atgrid (int y, int x) {
返回网格[y][x];
}

char * collect_points (const Pointgrp & pts) {
char * temp = new char [15];
*温度 = 0;
for (int pix = 0; pix < pts.len; ++pix) {
字符部分 [3] = "*";
常量点&mypt = pts.points[pix];
部分[0] = atgrid(mypt.y, mypt.x);
strcat(临时, 部分);
}
返回温度;
}

void run_partial(Pointgrp 组){
Pointgrp newgrp = group;
if (group.len >= 4) {
char * str = collect_points(组);
bool dbgf = false;

if (0 == memcmp(str,search_for,search_len)) {
//dbgf = true;
字数++;
}

如果 (dbgf) {
puts("积分:");
newgrp.print();
放(str);
}
删除[] str;
返回;
}

见过 * 见过obj = 新见过;
看到obj->init(newgrp);

点与lastpt = group.points[group.len-1];
点与newpt = newgrp.points[group.len];
newgrp.len++;

for (int yi = -1; yi <2; ++yi) {
for (int xi = -1; xi < 2; ++xi) {
if (0 == yi && 0 == xi) { 继续;}
//printf("(%d,%d)", yi, xi);
newpt.set(lastpt.y + yi, lastpt.x + xi);
if (!newpt.inbounds()) { 继续;}
if (seenobj->posPoint(newpt)) { 继续;}
run_partial(newgrp);
}
//puts("");
}

删除看到的obj;
}

无效运行(int y,int x){
点pt(y,x);
点grp grp;

grp.len = 1;
grp.points[0] = pt;
run_partial(grp);
}

void load_game (int num) {
静态字符 ** 游戏 [] = { yoyo1, yoyo2, yoyo3 };
int ndx;
网格 = 游戏[num-1];

maxx = 0;
for (ndx = 0; 网格[ndx][0]; ++ndx) {
int len = strlen(grid[ndx]);
if (len maxx) { maxx = len;}
}
最大 = ndx;
}

//------------------------------

int main (void)
{
load_game(3);

for (int row = 0; row < maxy; ++row) {
for (int col = 0; col < maxx; ++col) {
运行(行,列);
}
}
printf("字数 = %d\n", 字数);
返回0;
}

----------结束---------------

我使用递归是因为这是我能想到的唯一方法
解决方案,但现在我想删除递归,因为我需要
要在 Perl-Tk 程序的事件循环中完成的操作 :-)

我已经用 Perl-Tk 写过这个程序,但是递归
当程序计数 YOYOs 与有一个冲突时发生
响应式 GUI 界面.IOW,程序有时会冻结.

C++ 程序本质上与 Perl-Tk 程序做同样的事情
但没有图形用户界面.我创建了 C++ 程序来摆脱无关
与我的核心问题无关的东西——摆脱的需要
递归.

我知道/has/对此有一个迭代解决方案
问题——可能涉及堆栈,但我无法开始合并任何
想法.有人可以帮我从这个程序中删除递归吗?
--
数一数 YOYO:
http://home.earthlink.net/~mumia.w.18.spam/games_fever/

推荐答案

4月13日,凌晨 4 点 30 分,"Mumia W."<paduille.4061.mumia.w
+nos...@earthlink.net 写道:
大家好.

我有一个 C++ 程序,可以计算网格中的 YOYOs
Y 和 O.比如这个

哟哟哟哟哟
哦哦哦哦哦
哟哟哟哟哟
哦哦哦哦哦
O Y Y O Y O

应该有 406 YOYO's 在里面.YOYO's 一个上、下、右、左带
弯曲和对角线.

我的程序运行良好,但它使用递归,我想工作
迭代地.
我错过了什么?

对于网格中的每个字符:
对于每个周围的相反字符:
对于每个周围的相反字符:
对于每个周围的相反字符:
"找到悠悠球"


4 月 13 日上午 7:16,dave_mikes...@fastmail.fm 写道:
4 月 13 日凌晨 4 点 30 分,"Mumia W."<paduille.4061.mumia.w

+nos...@earthlink.net 写道:
大家好.
我有一个 C++ 程序,可以计算网格中的 YOYOs
Y 和 O.例如,这个
哟哟哟哟哟
哦哦哦哦哦
哟哟哟哟哟
哦哦哦哦哦
哟哟哟哟哟
应该有 406 YOYO's 在里面.YOYO's 一个上、下、右、左带
弯曲和对角线.
我的程序运行良好,但它使用递归,我想工作
迭代地.

我错过了什么?

对于网格中的每个字符:
对于每个周围的相反字符:
对于每个周围的相反字符:
对于每个周围的相反字符:
"找到悠悠球"-隐藏引用的文字-

- 显示引用的文字 -
请注意,以上将意第绪语版本("OYOY")解决为
好.;-)


da***********@fastmail.fm 写道:
4 月 13 日凌晨 4 点 30 分,"Mumia W.">我的程序运行良好,但它使用递归,我想迭代地工作
.

我错过了什么?

对于网格中的每个字符:
对于每个周围的相反字符:
对于每个周围的相反字符:
对于每个周围的相反字符:
"找到悠悠球"
确实,当递归深度固定时,内联应该是可能的
;-) 但你应该包括一些"见过"的东西.数组以便不使用任何字段
在同一个词中出现两次(例如,您从"Y O"中产生 yoyo)

但是,更通用的解决方案是使用 FIFO 和 push/pop
包含要访问的字段和当前深度的状态.

马库斯

本文地址:https://www.itbaoku.cn/post/1050467.html