nofm.htm

来自「“常见程式演算”主要收集一些常见的程式练习题目」· HTM 代码 · 共 144 行

HTM
144 行
字号 
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>





  
  
  
  
  
  <link rel="stylesheet" href="css/stdlayout.css" type="text/css">





  
  
  
  
  
  <link rel="stylesheet" href="css/print.css" type="text/css">





  
  
  
  
  
  <meta content="text/html; charset=gb2312" http-equiv="content-type">





  
  
  
  
  
  <title>m元素集合的n个元素子集</title>
</head>


<body>





<h3><a href="http://caterpillar.onlyfun.net/GossipCN/index.html">From
Gossip@caterpillar</a></h3>





<h1><a href="AlgorithmGossip.htm">Algorithm Gossip:&nbsp;m元素集合的n个元素子集</a></h1>





<h2>说明</h2>

假设有个集合拥有m个元素，任意的从集合中取出n个元素，则这n个元素所形成的可能子集有那些？<br>

<h2>解法</h2>

假设有5个元素的集点，取出3个元素的可能子集如下：<br>

<div style="margin-left: 40px; font-family: Courier New,Courier,monospace;"><span style="font-weight: bold;">{1 2 3}、{1 2 4 }、{1 2 5}、{1 3 4}、{1 3 5}、{1 4 5}、{2 3 4}、{2 3 5}、{2 4 5}、{3 4 5}</span><br>

</div>

<br>

这些子集已经使用字典顺序排列，如此才可以观察出一些规则：<br>

<ol>

  <li>如果最右一个元素小于m，则如同码表一样的不断加1</li>

  <li>如果右边一位已至最大值，则加1的位置往左移</li>

  <li>每次加1的位置往左移后，必须重新调整右边的元素为递减顺序</li>

</ol>

<br>

所以关键点就在于哪一个位置必须进行加1的动作，到底是最右一个位置要加1？还是其它的位置？<br>

<br>

在实际撰写程式时，可以使用一个变数positon来记录加1的位置，position的初值设定为n-1，因为我们要使用阵列，而最右边的索引值为最大
的n-1，在position位置的值若小于m就不断加1，如果大于m了，position就减1，也就是往左移一个位置；由于位置左移后，右边的元素会
经过调整，所以我们必须检查最右边的元素是否小于m，如果是，则position调整回n-1，如果不是，则positon维持不变。 <br>

<h2> 实作</h2>


<ul>

  <li> C
  </li>

</ul>


<pre>#include &lt;stdio.h&gt; <br>#include &lt;stdlib.h&gt; <br><br>#define MAX 20 <br><br>int main(void) { <br>    int set[MAX]; <br>    int m, n, position; <br>    int i; <br><br>    printf("输入集合个数 m："); <br>    scanf("%d", &amp;m); <br>    printf("输入取出元素 n："); <br>    scanf("%d", &amp;n); <br><br>    for(i = 0; i &lt; n; i++) <br>        set[i] = i + 1; <br><br>    // 显示第一个集合 <br>    for(i = 0; i &lt; n; i++) <br>        printf("%d ", set[i]); <br>    putchar('\n'); <br>    <br>    position = n - 1; <br><br>    while(1) { <br>        if(set[n-1] == m) <br>            position--; <br>        else <br>            position = n - 1; <br><br>        set[position]++; <br><br>        // 调整右边元素 <br>        for(i = position + 1; i &lt; n; i++) <br>            set[i] = set[i-1] + 1; <br><br>        for(i = 0; i &lt; n; i++) <br>            printf("%d ", set[i]); <br>        putchar('\n'); <br><br>        if(set[0] &gt;= m - n + 1) <br>            break; <br>    } <br><br>    return 0; <br>} <br></pre>


<br>


<ul>

  <li> Java
  </li>

</ul>


<pre>public class NofM {<br>    private int m;<br>    private int[] set;<br>    private boolean first;<br>    private int position;<br>    <br>    public NofM(int n, int m) {<br>        this.m = m;<br>        first = true;<br>        position = n - 1; <br><br>        set = new int[n];<br>        for(int i = 0; i &lt; n; i++) <br>            set[i] = i + 1; <br>    }<br>    <br>    public boolean hasNext() {<br>        return set[0] &lt; m - set.length + 1;<br>    }<br>    <br>    public int[] next() {<br>        if(first) {<br>            first = false;<br>            return set;<br>        }<br>        <br>        if(set[set.length-1] == m) <br>            position--; <br>        else <br>            position = set.length - 1; <br><br>        set[position]++; <br><br>        // 调整右边元素 <br>        for(int i = position + 1; i &lt; set.length; i++) <br>            set[i] = set[i-1] + 1;<br>        <br>        return set;<br>    }<br>    <br>    public static void main(String[] args) {<br>        NofM nOfm = new NofM(3, 5);<br>        <br>        while(nOfm.hasNext()) {<br>            int[] set = nOfm.next();<br>            for(int i = 0; i &lt; set.length; i++) {<br>                System.out.print(set[i]);   <br>            }<br>            System.out.println();<br>        }<br>    }<br>}</pre>

<br>


<br>





</body>
</html>

nofm.htm - 源码说明

本页面展示了「“常见程式演算”主要收集一些常见的程式练习题目」中的 nofm.htm 源码文件，采用 HTM 编程语言编写，共 144 行代码。您可以在线阅读完整代码内容，也可以返回资源详情页下载完整源码包进行本地学习和开发。

虫虫开发者社区收录了大量与算法练习相关的技术资源，包括源代码、技术文档、电路图等，是电子工程师和嵌入式开发者的专业学习平台。

⌨️ 快捷键说明

复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?