删除递归 [英] Removing recursion
问题描述
大家好。
我有一个C ++程序，可以计算网格中的YOYO
Y'和O''秒。例如，这个
YOYOOY
OYOYOO
YOYYOY
OYOOYO
OYYOYO
应该有406 YOYO'。 YOYO是一个上，下，左右两个，有
弯曲和对角线。
我的程序运行良好，但它使用递归，我想要工作
迭代。
这是程序：
#include< stdio.h>
#include< stdlib.h>
#include< string.h>
#include< ctype.h>
const int max_points = 10;
extern int maxy，maxx;
struct Point {
int y;
int x;
Point（）{y = x = 0; } $ / $
Point（int ey，int ex）{y = ey; x = ex; }
void set（int ey，int ex）{y = ey; x = ex; }
bool inbounds（）{
if（y< 0 || y> = maxy）{return false; }
if（x< 0 || x> = maxx）{return false; }
返回true;
}
char * as_string（）{
char * temp = new char [ 10];
sprintf（temp，"（％d，％d）"，y，x）;
return temp;
}
void print（）{printf（"％s"，as_string（））; }
};
struct Pointgrp {
int len;
点数[max_points] ;
void print（）{
for（int pos = 0; pos< len; ++ pos）{
points [pos ] .print（）;
}
puts（""）;
}
};
struct查看{
char数据[1000];
Seen（）{clear（）; }
void clear（）{memset（data，0，sizeof（data））; }
char& pos（int y，int x）{
返回数据[（y * maxx）+ x];
}
void init（const Pointgrp& pts）{
for（int pix = 0; pix< pts.len; ++ pix）{
const Point& mypt = pts.points [pix];
pos（mypt.y，mypt.x）= 1;
}
}
char& posPoint（const Point& pt）{
pos（pt.y，pt.x）;
}
};
char * yoyo1 [] = {
" YOY"，
" YOYOO"，
" OYYOYYO"，
" OYYYO"，
" YOY"，
""，
};
char * yoyo2 [] = {
" YO"，
" OY"，
""，
};
char * yoyo3 [] = {
" YOYOOY"，
" OYOYOO"，
" YOYYOY"，
" OYOOYO"，
" OYYOYO"，
""，
};
char ** grid = yoyo1;
int maxx = 7;
int maxy = 5;
const char * search_for =" YOYO";
int search_len = 4;
int wordcount = 0;
// ----------------------------------------- -
char& atgrid（int y，int x）{
返回网格[y] [x];
}
char * collect_points （const Pointgrp& pts）{
char * temp = new char [15];
* temp = 0;
for（int pix = 0; pix< pts.len; ++ pix）{
char part [3] =" *" ;;
const Point& mypt = pts.points [pix];
part [0] = atgrid（mypt.y，mypt.x）;
strcat（temp，part）;
}
返回临时;
}
void run_partial（Pointgrp group）{
Pointgrp newgrp = group;
if（group.len> = 4）{
char * str = collect_points（group）;
bool dbgf = false;
if（0 == memcmp（str，search_for，search_len））{
// dbgf = true;
wordcount ++;
}
if（dbgf）{
puts（" Points："） ;）;
newgrp.print（）;
puts（str）;
}
delete [] str;
返回;
}
Seen * seenobj = new Seen;
seenobj- > init（newgrp）;
Point& lastpt = group.points [group.len-1];
Point& 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（））{continue; }
if（seenobj-> posPoint（newpt））{continue; }
run_partial（newgrp）;
}
// puts（""）;
}
删除seenobj;
}
void run（int y，int x）{
Point pt（y，x）;
Pointgrp grp;
grp.len = 1;
grp .points [0] = pt;
run_partial（grp）;
}
void load_game（int num）{
静态char **游戏[] = {yoyo1，yoyo2，yoyo3};
int ndx;
grid = games [num-1] ;
maxx = 0;
for（ndx = 0; grid [ndx] [0]; ++ ndx）{
int len = strlen（grid [ndx]）;
if（len maxx）{maxx = len; }
}
maxy = ndx;
}
// ----- -------------------------------------
int main（无效）
{
load_game（3）;
for（int row = 0; row< maxy; （+行）{
for（int col = 0; col< maxx; ++ col）{
run（row，col）;
}
}
printf（" Wordcount =％d \ n"，wordcount）;
返回0;
}
----------------------结束-------- -------
我使用了递归，因为这是我能设想一个
解决方案的唯一方法，但现在我想删除递归因为我需要在Perl-Tk程序的事件循环中完成
操作:-)
我已经编写了这个程序在Perl-Tk中，但是当程序计算YOYO与具有
响应式GUI界面的冲突时，会发生
的递归。 IOW，该程序有时会冻结。
C ++程序与Perl-Tk程序基本相同
但没有GUI。我创建了C ++程序，以摆脱与我的核心问题无关的无关的
的东西 - 需要摆脱
递归。
我知道/有/这是一个迭代解决方案来解决这个问题 - 可能涉及堆栈，但我不能开始合并任何
想法。有人可以帮我删除这个程序的递归吗？
-
算上YOYO：
http://home.earthlink.net/~mumia.w.18.spam/games_fever/
4月13日凌晨4:30，Mumia W. < paduille.4061.mumia.w
+ nos ... @ earthlink.netwrote：
Hello all。
我有一个C ++程序，可以计算在
Y'和O'的网格中的YOYO。例如，这个
YOYOOY
OYOYOO
YOYYOY
OYOOYO
OYYOYO
应该有406 YOYO'。 YOYO是一个上，下，左右两个，有
弯曲和对角线。
我的程序运行良好，但它使用递归，我想要迭代地工作
。
我缺少什么？
网格中每个字符的
：
每个周围的
对面的char：
每个周围的对面字符：
每个周围的对面字符：
" found yoyo"
4月13日上午7:16，dave_mikes ... @ fastmail.fm写道：
4月13，凌晨4:30，Mumia W. < paduille.4061.mumia.w
+ nos ... @ earthlink.netwrote：
大家好。
我有一个C ++程序可以计算在
Y'和O的网格中的YOYO '的。例如，这个
YOYOOY
OYOYOO
YOYYOY
OYOOYO
OYYOYO
应该有406 YOYO'。 YOYO'上下左右，有
弯曲和对角线。
我的程序运行良好，但它使用递归，我想迭代地工作
。
我缺少什么？
网格中每个字符的
：每个周围的
相反的字符：
每个周围的对面字符：
每个周围的对面字符：
" found yoyo" - 隐藏引用的文字 - < br b> b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b />
好吧。 ;-)
da ** *********@fastmail.fm 写道：
4月13日凌晨4:30，Mumia W. ; < paduille.4061.mumia.w
>我的程序运行良好，但它使用递归，我想迭代地工作。
我缺少什么？
网格中每个字符的
：每个周围的
对面的char：
每个周围的对面字符：
每个周围的对面字符：
" found yoyo"
实际上，当递归深度固定时，内联应该是可能的
;-)但是你应该包括一些看到的东西。数组，以便在同一个单词中不使用任何字段
（例如，您从Y O生成yoyo）
然而，更通用的解决方案将使用FIFO和推/弹
状态包含要访问的字段和当前深度。
Markus
Hello all.
I have a C++ program that can count the YOYOs that are in a grid of
Y''s and O''s. For example, this
Y O Y O O Y
O Y O Y O O
Y O Y Y O Y
O Y O O Y O
O Y Y O Y O
should have 406 YOYO''s in it. YOYO''s an go up, down, right and left with
bends and diagonals.
My program works great, but it uses recursion, and I want to work
iteratively.
Here is the program:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
const int max_points = 10;
extern int maxy, maxx;
struct Point {
int y;
int x;
Point () { y = x = 0; }
Point (int ey, int ex) { y = ey; x = ex; }
void set (int ey, int ex) { y = ey; x = ex; }
bool inbounds() {
if (y < 0 || y >= maxy) { return false; }
if (x < 0 || x >= maxx) { return false; }
return true;
}
char * as_string() {
char * temp = new char [10];
sprintf(temp, "(%d,%d)", y, x);
return temp;
}
void print() { printf("%s ", as_string()); }
};
struct Pointgrp {
int len;
Point points [max_points];
void print () {
for (int pos = 0; pos < len; ++pos) {
points[pos].print();
}
puts("");
}
};
struct Seen {
char data [1000];
Seen() { clear(); }
void clear() { memset(data,0,sizeof(data)); }
char & pos(int y, int x) {
return data[(y * maxx) + x];
}
void init(const Pointgrp & pts) {
for (int pix = 0; pix < pts.len; ++pix) {
const Point & mypt = pts.points[pix];
pos(mypt.y, mypt.x) = 1;
}
}
char & posPoint(const Point & pt) {
pos(pt.y, pt.x);
}
};
char * yoyo1 [] = {
" YOY ",
" YOYOO ",
"OYYOYYO",
" OYYYO ",
" YOY ",
"",
};
char * yoyo2 [] = {
"YO",
"OY",
"",
};
char * yoyo3 [] = {
"YOYOOY",
"OYOYOO",
"YOYYOY",
"OYOOYO",
"OYYOYO",
"",
};
char ** grid = yoyo1;
int maxx = 7;
int maxy = 5;
const char * search_for = "YOYO";
int search_len = 4;
int wordcount = 0;
// ------------------------------------------
char & atgrid (int y, int x) {
return grid[y][x];
}
char * collect_points (const Pointgrp & pts) {
char * temp = new char [15];
*temp = 0;
for (int pix = 0; pix < pts.len; ++pix) {
char part [3] = "*";
const Point & mypt = pts.points[pix];
part[0] = atgrid(mypt.y, mypt.x);
strcat(temp, part);
}
return temp;
}
void run_partial (Pointgrp group) {
Pointgrp newgrp = group;
if (group.len >= 4) {
char * str = collect_points(group);
bool dbgf = false;
if (0 == memcmp(str,search_for,search_len)) {
// dbgf = true;
wordcount++;
}
if (dbgf) {
puts("Points:");
newgrp.print();
puts(str);
}
delete[] str;
return;
}
Seen * seenobj = new Seen;
seenobj->init(newgrp);
Point & lastpt = group.points[group.len-1];
Point & 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) { continue; }
// printf("(%d,%d) ", yi, xi);
newpt.set(lastpt.y + yi, lastpt.x + xi);
if (! newpt.inbounds()) { continue; }
if (seenobj->posPoint(newpt)) { continue; }
run_partial(newgrp);
}
// puts("");
}
delete seenobj;
}
void run (int y, int x) {
Point pt(y,x);
Pointgrp grp;
grp.len = 1;
grp.points[0] = pt;
run_partial(grp);
}
void load_game (int num) {
static char ** games [] = { yoyo1, yoyo2, yoyo3 };
int ndx;
grid = games[num-1];
maxx = 0;
for (ndx = 0; grid[ndx][0]; ++ndx) {
int len = strlen(grid[ndx]);
if (len maxx) { maxx = len; }
}
maxy = ndx;
}
// ------------------------------------------
int main (void)
{
load_game(3);
for (int row = 0; row < maxy; ++row) {
for (int col = 0; col < maxx; ++col) {
run(row, col);
}
}
printf("Wordcount = %d\n", wordcount);
return 0;
}
----------------------end---------------
I used recursion because that was the only way I could envision a
solution, but now I want to remove the recursion because I need the
operations to be done in the event-loop of a Perl-Tk program :-)
I''ve already written this program in Perl-Tk, but the recursion that
occurs when the program is counting YOYOs conflicts with having a
responsive GUI interface. IOW, the program freezes at times.
The C++ program does essentially the same thing as the Perl-Tk program
but without the GUI. I created the C++ program to get rid of extraneous
stuff that doesn''t relate to my core problem--the need to get rid of
recursion.
I know that there /has/ to be an iterative solution for this
problem--probably involving a stack, but I can''t begin to coalesce any
ideas. Can someone help me remove the recursion from this program?
--
Count the YOYOs:
http://home.earthlink.net/~mumia.w.18.spam/games_fever/
解决方案On Apr 13, 4:30 am, "Mumia W." <paduille.4061.mumia.w
+nos...@earthlink.netwrote:Hello all.
I have a C++ program that can count the YOYOs that are in a grid of
Y''s and O''s. For example, this
Y O Y O O Y
O Y O Y O O
Y O Y Y O Y
O Y O O Y O
O Y Y O Y O
should have 406 YOYO''s in it. YOYO''s an go up, down, right and left with
bends and diagonals.
My program works great, but it uses recursion, and I want to work
iteratively.What am I missing?
for each char in grid:
for each surrounding opposite char:
for each surrounding opposite char:
for each surrounding opposite char:
"found yoyo"
On Apr 13, 7:16 am, dave_mikes...@fastmail.fm wrote:On Apr 13, 4:30 am, "Mumia W." <paduille.4061.mumia.w
+nos...@earthlink.netwrote:Hello all.
I have a C++ program that can count the YOYOs that are in a grid of
Y''s and O''s. For example, this
Y O Y O O Y
O Y O Y O O
Y O Y Y O Y
O Y O O Y O
O Y Y O Y O
should have 406 YOYO''s in it. YOYO''s an go up, down, right and left with
bends and diagonals.
My program works great, but it uses recursion, and I want to work
iteratively.
What am I missing?
for each char in grid:
for each surrounding opposite char:
for each surrounding opposite char:
for each surrounding opposite char:
"found yoyo"- Hide quoted text -
- Show quoted text -Note that the above will solve the Yiddish version ("OYOY") as
well. ;-)
da***********@fastmail.fm wrote:On Apr 13, 4:30 am, "Mumia W." <paduille.4061.mumia.w>My program works great, but it uses recursion, and I want to work
iteratively.
What am I missing?
for each char in grid:
for each surrounding opposite char:
for each surrounding opposite char:
for each surrounding opposite char:
"found yoyo"Indeed, inlining should be possible when the recursion depth is fixed
;-) But you should include some "seen" array so that no field is used
twice within the same word (e.g. you produce yoyo from "Y O")
However, the more general solution would be to use a FIFO and push/pop
states containing the field to visit and the current depth.
Markus
这篇关于删除递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
