00001
00021 #include "mfcpch.h"
00022 #include <stdio.h>
00023 #include <stdlib.h>
00024 #include "errcode.h"
00025
00026 #define f(xc, yc) ((xc - factor*yc)*(xc - factor*yc))
00027
00028 #define g(oldyc, yc, oldxc, xc) (factor*factor*(oldyc - yc)*(oldyc - yc)/(abs(oldxc - xc) + 1))
00029
00030 void
00031 dyn_exit (const char s[]) {
00032 fprintf (stderr, "%s", s);
00033 err_exit();
00034 }
00035
00036
00048 void dyn_prog(
00049 int n,
00050 int *x,
00051 int *y,
00052 int ymax,
00053 int *oldx,
00054 int *oldy,
00055 int oldn,
00056 float factor) {
00057 int i, z, j, matchflag;
00058 int **ymin;
00059 float **F, fz;
00060
00061
00062
00063 F = (float **) calloc (n, sizeof (float *));
00064 ymin = (int **) calloc (n, sizeof (int *));
00065 if ((F == NULL) || (ymin == NULL))
00066 dyn_exit ("Error in calloc\n");
00067
00068 for (i = 0; i < n; i++) {
00069 F[i] = (float *) calloc (ymax - n + i + 1, sizeof (float));
00070 ymin[i] = (int *) calloc (ymax - n + i + 1, sizeof (int));
00071 if ((F[i] == NULL) || (ymin[i] == NULL))
00072 dyn_exit ("Error in calloc\n");
00073 }
00074
00075 F[0][0] = f (x[0], 0);
00076
00077 j = 0;
00078 while ((j < oldn) && (oldx[j] < x[0]))
00079 j += 2;
00080 if (j >= oldn)
00081 j -= 2;
00082 else if ((j - 2 >= 0) && ((x[0] - oldx[j - 2]) < (oldx[j] - x[0])))
00083 j -= 2;
00084 if (abs (oldx[j] - x[0]) < factor) {
00085 matchflag = 1;
00086 F[0][0] += g (oldy[j], 0, oldx[j], x[0]);
00087 }
00088 else
00089 matchflag = 0;
00090 ymin[0][0] = 0;
00091
00092 for (z = 1; z < ymax - n + 1; z++) {
00093 fz = f (x[0], z);
00094
00095 if (matchflag)
00096 fz += g (oldy[j], z, oldx[j], x[0]);
00097 if (fz < F[0][z - 1]) {
00098 F[0][z] = fz;
00099 ymin[0][z] = z;
00100 }
00101 else {
00102 F[0][z] = F[0][z - 1];
00103 ymin[0][z] = ymin[0][z - 1];
00104 }
00105 }
00106
00107 for (i = 1; i < n; i++) {
00108 F[i][i] = f (x[i], i) + F[i - 1][i - 1];
00109
00110 if (j > 0)
00111 j--;
00112 else
00113 j++;
00114 while ((j < oldn) && (oldx[j] < x[i]))
00115 j += 2;
00116 if (j >= oldn)
00117 j -= 2;
00118 else if ((j - 2 >= 0) && ((x[i] - oldx[j - 2]) < (oldx[j] - x[i])))
00119 j -= 2;
00120 if (abs (oldx[j] - x[i]) < factor) {
00121 matchflag = 1;
00122 F[i][i] += g (oldy[j], i, oldx[j], x[i]);
00123 }
00124 else
00125 matchflag = 0;
00126 ymin[i][i] = i;
00127 for (z = i + 1; z < ymax - n + i + 1; z++) {
00128 fz = f (x[i], z) + F[i - 1][z - 1];
00129
00130 if (matchflag)
00131 fz += g (oldy[j], z, oldx[j], x[i]);
00132 if (fz < F[i][z - 1]) {
00133 F[i][z] = fz;
00134 ymin[i][z] = z;
00135 }
00136 else {
00137 F[i][z] = F[i][z - 1];
00138 ymin[i][z] = ymin[i][z - 1];
00139 }
00140 }
00141 }
00142
00143 y[n - 1] = ymin[n - 1][ymax - 1];
00144 for (i = n - 2; i >= 0; i--)
00145 y[i] = ymin[i][y[i + 1] - 1];
00146
00147 for (i = 0; i < n; i++) {
00148 free (F[i]);
00149 free (ymin[i]);
00150 }
00151 free(F);
00152 free(ymin);
00153
00154 return;
00155 }