Whi*_*ity 6 c# algorithm recursion struct solver
我一直在干扰C#中的一个想法来创建一个软件(用于伪个人使用),但遇到了实现问题.嗯......也许他们是我不知道的设计问题,但我只是简直无法弄清楚.
考虑我们有以下"数据库":
Foo + Bar = Foobar
Baz + Qux = Bazqux
Foobar + Bazqux = Foobarbazqux
这些是用于创建所述项目的配方.使用一个和一个,我们创建一个结果,可以进一步成为另一个食谱的成分.FooBarFoobar
现在想我们需要找出该项目的完整配方Foobarbazqux.对于人类的思想和智慧,它相对容易:
We need Foobarbazqux
Foobarbazqux = Foobar + Bazqux
Foobar = Foo + Bar
Bazqux = Baz + Qux
Foobarbazqux = Foo + Bar + Baz + Qux
当然,如果我们拥有所有成分,我们可以"运行" 配方,并按照上面几段的顺序创建项目并执行每个配方.(那样:我们首先创建Foobar,然后Bazqux将两者结合起来得到最终结果.)
但在现实的时候,数据库是很多大.我想这就是计算机应该进入的地方.通过一个可用的软件,机器可以轻松找到所有的成分和执行(制作)步骤并将其提供给用户,因此我们不需要通过所有条目来读取手.
我曾考虑使用C#来实现这个软件.命令行项目,没什么光泽或任何东西,只是纯粹的stdio.
首先,当然,我需要定义该项目.(注意:现在我考虑使用结构,但如果需要,我可以将它们"升级"为类."数据库"是从某种顺序文本文件初始化的,这将在以后制作."数据库"不会被修改或者在执行期间或之后以任何方式编写,一旦加载,它就是只读的.)当然,我需要定义配方.
struct Item
{
public string Name;
}
struct Recipe
{
public Item Result;
public Item[] Ingredients;
}
这两个结构保存在(默认类)的通用static List<>字段中Program.
在入口点,我们定义了一些项目和一些测试配方:
items.Add(new Item { Name = "Foo" });
items.Add(new Item { Name = "Bar" });
items.Add(new Item { Name = "Baz" });
items.Add(new Item { Name = "Qux" });
items.Add(new Item { Name = "Foobar" });
items.Add(new Item { Name = "Bazqux" });
items.Add(new Item { Name = "Foobarbazqux" });
recipes.Add(new Recipe
{
Result = GetItem("Foobar"),
Ingredients = new Item[] { GetItem("Foo"), GetItem("Bar") }
});
recipes.Add(new Recipe
{
Result = GetItem("Bazqux"),
Ingredients = new Item[] { GetItem("Baz"), GetItem("Qux") }
});
recipes.Add(new Recipe
{
Result = GetItem("Foobarbazqux"),
Ingredients = new Item[] { GetItem("Foobar"), GetItem("Bazqux") }
});
由于项目是由其Name字段主键控的,GetItem因此只是一个List.Find<>快捷方式:
private static Item GetItem(string _name)
{
return Program.Items.Find(match => match.Name == _name);
}
所以现在,数据库已经设置好了.我已经意识到我需要制作某种递归方法来获取所有成分,但这就是我遇到问题的地方.
考虑以下,第一次尝试(这不是递归,只是"一级深"):
string search = "Foobarbazqux";
SearchRecipe(search);
private static void SearchRecipe(string _search)
{
List<Recipe> item_recipes = Program.Recipes.FindAll(match => match.result.Name == GetItem(search).Name);
foreach (Recipe recp in item_recipes)
{
Console.WriteLine("-------------");
Console.WriteLine("Ingredients: ");
foreach (Item ingredient in recp.Ingredients)
{
Console.WriteLine(ingredient.Name);
}
}
}
这会产生以下输出,即没有递归,非常好并且预期:
-------------
Ingredients:
Foobar
Bazqux
所以对于递归,我修改了这样的代码:
foreach (Item ingredient in recp.Ingredients)
{
+++ if (recipes.FindAll(match2 => match2.Result.name == Ingredient.name).Count != 0)
+++ {
+++ SearchRecipe(ingredient.Name);
+++ }
Console.WriteLine(ingredient.Name);
}
现在输出如下:
| -------------
| Ingredients:
* -------------
* Ingredients:
* Foo
* Bar
| Foobar
@ -------------
@ Ingredients:
@ Baz
@ Qux
| Bazqux
我看到当我理解我的代码时会发生什么.标*有的行是递归Foobar,@是递归Bazqux,|是原始方法调用的输出.但这不是......有点我想要实现的输出,因为它不容易理解,而且......通常不正确.
我可视化的输出类似于以下内容(当然"额外"状态行是可忽略的):
Searching for: Foobarbazqux
1 recipe found.
-----
1 Foobarbazqux = 1 Foobar + 1 Bazqux
1 Foobar = 1 Foo + 1 Bar
1 Bazqux = 1 Baz + 1 Qux
1 Foobarbazqux = 1 Foo + 1 Bar + 1 Baz + 1 Qux
1 Foo + 1 Bar => 1 Foobar
1 Baz + 1 Qux => 1 Bazqux
1 Foobar + 1 Bazqux => 1 Foobarbazqux
-----
Exit.
这就是我所说的打破该项目创造链的食谱......或者......我不叫,但可以想象这样,在参考了问题的称号.所以程序的工作原理如下:
Foobarbazqux在我们的示例中)ResultRecipe注意:更好地适应真实场景,但会产生额外的实现差距:大部分项目都有多个可以创建它们的配方.
我想要求的是建议和帮助.我慢慢地想要说服自己这个程序是不可写的(这只是某种绝望的呐喊)而且我的想法有设计问题.但我仍然希望,在界限内,我们不需要花哨但尚未创建的人工智能系统来解决这个......有点低估的问题.
谢谢.
第二个答案，针对“从头开始重写”的方法。如果只给出没有先前代码的问题陈述，这或多或少是我的做法。
abstract class Item
{
public string Name { get; private set; }
public abstract IEnumerable<Item> Ingredients { get; }
public abstract IEnumerable<Item> ParseRecipe();
protected Item(string name)
{
Name = name;
}
public static Item GetItem(string _name)
{
return items.Find(match => match.Name == _name);
}
}
class Atom : Item
{
public Atom(string name) : base(name) { }
public override IEnumerable<Item> Ingredients { get { return null; } }
public override IEnumerable<Item> ParseRecipe()
{
return new[] { this };
}
}
class Recipe : Item
{
public Recipe(string name, params Item[] ingredients) : base(name)
{
_ingredients = ingredients;
}
public Recipe(string name, params string[] ingredients) : base(name)
{
_ingredients = ingredients.Select(x => Item.GetItem(x));
}
private IEnumerable<Item> _ingredients;
public override IEnumerable<Item> Ingredients { get { return _ingredients;} }
public override IEnumerable<Item> ParseRecipe()
{
Console.WriteLine("1 " + this.Name + " = "
+ String.Join(" + ", this.Ingredients.Select(x => "1 " + x.Name)));
var components = new List<Item>();
foreach(var ing in Ingredients)
{
components.AddRange(ing.ParseRecipe());
}
return components;
}
}
用法如下：
void Main()
{
items.Add(new Atom("Foo"));
items.Add(new Atom("Bar"));
items.Add(new Atom("Baz"));
items.Add(new Atom("Qux" ));
items.Add(new Recipe("Foobar", "Foo", "Bar"));
items.Add(new Recipe( "Bazqux", "Baz", "Qux" ));
items.Add(new Recipe( "Foobarbazqux", "Foobar", "Bazqux" ));
string search = "Foobarbazqux";
var item = Item.GetItem(search);
Console.WriteLine("1 " + item.Name + " = "
+ String.Join(" + ", item.ParseRecipe().Select(x => "1 " + x.Name)));
}
结果是：
1 Foobarbazqux = 1 Foobar + 1 Bazqux
1 Foobar = 1 Foo + 1 Bar
1 Bazqux = 1 Baz + 1 Qux
1 Foobarbazqux = 1 Foo + 1 Bar + 1 Baz + 1 Qux
与原始代码相比，此方法的主要优点与abstract class Item. 这样，我们只关心初始化时Atoms和Recipes之间的差异。之后，一切都被视为Item. 这意味着递归变得更加简单，因为我们不关心当前项目Ingredients是原子的、食谱还是它们的混合。这也意味着您可以调用SearchRecipe()任何内容，而无需检查它是否确实是Recipe第一个。 （请注意，我稍微编辑了上面的代码，以便在这种情况下获得更好的输出。）
这对于 a 来说是不可能的struct，因为它们不能相互继承，因此不能被视为父类型。您可以声明interface它们都将实现，但根据此，当您将其转换为接口时，您会失去大部分内存优势struct，而我们一直都会这样做。