subject_44278.htm

vc

<p>
序号：44278 发表者：lee 发表日期：2003-06-18 11:17:45
<br>主题：来看看复式拆分算法
<br>内容：<BR>输入为“－”分割的任意长度字符串例如12-1-123-13<BR>求出排列组合拆分后的字符串组，如上式猜解为<BR>1-1-1-1<BR>1-1-1-3<BR>1-1-2-1<BR>1-1-2-3<BR>1-1-3-1<BR>1-1-3-3<BR>2-1-1-1<BR>2-1-1-3<BR>2-1-2-1<BR>2-1-2-3<BR>2-1-3-1<BR>2-1-3-3<BR>要求算法要优化高效，因为可能拆分结果高达百万级。<BR>各位老大帮帮忙呀
<br><a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p>
<hr size=1>
<blockquote><p>
回复者：lee 回复日期：2003-06-19 15:54:34
<br>内容：不好意思，是我没有解释清楚。<BR>比如上式输入的字符串12-1-123-13的含义是，<BR>一共有四个节点，第一个节点可能是1或者2，第二个节点只能为1，第三个节点可能为1或者2或者3，第四个节点可能为1或者3。<BR>那么拆分出所有可能的序列组合，<BR>比如第一节点选择1，第二节点因为只有一种选择为1，第三节点也选择1，第四节点也选择1，<BR>那么一种组合的情况是1－1－1－1；<BR>一共可以排列出上面写出的这些组合。<BR>
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
<font color=red>答案被接受</font><br>回复者：hsx 回复日期：2003-07-08 14:26:36
<br>内容：#include "stdio.h"<BR>#include "stdlib.h"<BR>#include "string.h"<BR><BR>char *array = "12-1-123-13";<BR><BR>void go(char *gg, int cc, unsigned int *pp, int *ppn, int nn)<BR>{<BR>&nbsp;&nbsp;&nbsp;&nbsp;int i;<BR>&nbsp;&nbsp;&nbsp;&nbsp;char *ppp =(char *)pp[nn];<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;if (0 == ppn[nn])<BR>&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for (i=0; i&lt;cc; i++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf("%c-",gg[i]);<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf("\n");<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return;<BR>&nbsp;&nbsp;&nbsp;&nbsp;}<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;for (i=0; i&lt;ppn[nn]; i++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;gg[cc] = ppp[i];<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;go(gg, cc+1, pp, ppn, nn+1);<BR>&nbsp;&nbsp;&nbsp;&nbsp;}<BR>}<BR><BR>void main()<BR>{<BR>&nbsp;&nbsp;&nbsp;&nbsp;int i, len, nindex = 0;<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;unsigned int *p;<BR>&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*n;<BR>&nbsp;&nbsp;&nbsp;&nbsp;char&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; *g;<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; //actually, len is the count of '-' in array<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // plus 1, but i am lazy, not calculate the<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; //count of '-';<BR>&nbsp;&nbsp;&nbsp;&nbsp;len = strlen(array);<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;p = new unsigned int[len];<BR>&nbsp;&nbsp;&nbsp;&nbsp;n = new int[len];<BR>&nbsp;&nbsp;&nbsp;&nbsp;g = new char[len];<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;for (i=0; i&lt;len; i++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p[i] = 0;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;n[i] = 0;<BR>&nbsp;&nbsp;&nbsp;&nbsp;}<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;p[nindex] = (unsigned int)array;<BR>&nbsp;&nbsp;&nbsp;&nbsp;for (i=0; i&lt;len; i++)<BR>&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if ('-' == array[i])<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;nindex++;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p[nindex] = (unsigned int)&amp;array[i+1];<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;continue;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;n[nindex]++;<BR>&nbsp;&nbsp;&nbsp;&nbsp;}<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;go(g, 0, p, n, 0);<BR><BR>&nbsp;&nbsp;&nbsp;&nbsp;delete[] p;<BR>&nbsp;&nbsp;&nbsp;&nbsp;delete[] n;<BR>&nbsp;&nbsp;&nbsp;&nbsp;delete[] g;<BR>}
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：lee 回复日期：2003-07-09 09:50:01
<br>内容：万分感谢
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>