(2010年08月03日 15:45), NIIBE Yutaka wrote: > ここは及第点とは言えない、というレベルではなく、明らかに落第点しかあげ > られない、という感じです。プンプン。
怒ったり嘆いていてばかりでもしかたがないので、少し書いてみました。 書いてみたら、参照にあげた http://mat.gsia.cmu.edu/classes/dynamic/node3.html の例に間違いが見つかりました。 /* * example code finding shortest path(s) in a trellis. * * Copyright (C) 2010 Free Software Initiative of Japan * Author: NIIBE Yutaka <gni...@fsij.org> * * You can use/modify/distribute under the license of GPLv3+. */ /* * example: * fixed version of http://mat.gsia.cmu.edu/classes/dynamic/node3.html * (cost from A to D is 3 (instead of 2)) * * (B) 7 (E) 1 * 4 (H) * 2 6 4 3 * * 3 6 * (A) 4 (C) 2 (F) (J) * 4 3 * * 3 3 4 * 4 (I) * 1 3 * (D) 5 (G) */ #include <assert.h> #include <stdlib.h> #include <stdio.h> #define MAX_COST 1000000 struct arc { struct node *node; int cost; }; struct node { struct node *next; const char *name; int min_cost; int num_arcs; struct arc arc[1]; }; static struct node * node_new (const char *name, int num_arcs, struct node *next) { struct node *node; int i; node = (struct node *)malloc (sizeof (struct node) + sizeof (struct arc) * (num_arcs - 1)); if (node == NULL) exit (1); node->name = name; node->min_cost = MAX_COST; node->next = next; node->num_arcs = num_arcs; for (i = 0; i < num_arcs; i++) { node->arc[i].node = NULL; node->arc[i].cost = MAX_COST; } return node; } static void calc_cost (struct node *node) { if (node != NULL) { int i, min_cost = MAX_COST; calc_cost (node->next); for (i = 0; i < node->num_arcs; i++) { int cost = node->arc[i].node->min_cost + node->arc[i].cost; if (cost < min_cost) min_cost = cost; } if (i == 0) node->min_cost = 0; else node->min_cost = min_cost; } } static void show_cost (struct node *node) { if (node != NULL) { printf ("%s: %d\n", node->name, node->min_cost); show_cost (node->next); } } static void show_paths (struct node *node, int depth) { if (node != NULL) { int i; for (i = 0; i < depth; i++) putchar (' '); printf ("%s\n", node->name); for (i = 0; i < node->num_arcs; i++) { int cost = node->arc[i].node->min_cost + node->arc[i].cost; if (cost == node->min_cost) show_paths (node->arc[i].node, depth + 1); } } } /* * Using compound literals of C99 for (struct arc). */ int main (void) { struct node *a, *b, *c, *d, *e, *f, *g, *h, *i, *j; a = node_new ("A", 3, NULL); b = node_new ("B", 3, NULL); a->next = b; a->arc[0] = (struct arc){ b, 2 }; e = node_new ("E", 2, NULL); b->next = e; b->arc[0] = (struct arc){ e, 7 }; h = node_new ("H", 1, NULL); e->next = h; e->arc[0] = (struct arc){ h, 1 }; j = node_new ("J", 0, NULL); h->next = j; h->arc[0] = (struct arc){ j, 3 }; i = node_new ("I", 1, h->next); i->arc[0] = (struct arc){ j, 4 }; h->next = i; e->arc[1] = (struct arc){ i, 4 }; f = node_new ("F", 2, e->next); f->arc[0] = (struct arc){ h, 6 }; f->arc[1] = (struct arc){ i, 3 }; e->next = f; b->arc[1] = (struct arc){ f, 4 }; g = node_new ("G", 2, f->next); g->arc[0] = (struct arc){ h, 3 }; g->arc[1] = (struct arc){ i, 3 }; f->next = g; b->arc[2] = (struct arc){ g, 6 }; c = node_new ("C", 3, b->next); c->arc[0] = (struct arc){ e, 3 }; c->arc[1] = (struct arc){ f, 2 }; c->arc[2] = (struct arc){ g, 4 }; b->next = c; a->arc[1] = (struct arc){ c, 4 }; d = node_new ("D", 3, c->next); d->arc[0] = (struct arc){ e, 4 }; d->arc[1] = (struct arc){ f, 1 }; d->arc[2] = (struct arc){ g, 5 }; c->next = d; a->arc[2] = (struct arc){ d, 3 }; calc_cost (a); show_cost (a); show_paths (a, 0); return (0); } -- _______________________________________________ Anthy-dev mailing list Anthy-dev@lists.sourceforge.jp http://lists.sourceforge.jp/mailman/listinfo/anthy-dev
