宋老师，这道题是这么做的，想了好久了，没想出来
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 20
int a[N];
void gen_random(int upper_bound)
{
int i;
srand(time(NULL));
for(i = 0;i < N;i++)
a[i] = rand() % upper_bound;
}
int howmany(int value)
{
int count = 0,i;
for(i = 0;i < N;i++)
if (a[i]==value)
++count;
return count;
}
int main(void)
{
int i,histogram[10] = {};
int j;
gen_random(10);
for(i = 0;i < N;i++)
++histogram[a[i]];
for(i = 0;i < 10;i++)
printf("%d\t",i);
printf("\n");
for(j = 0;j < N;j++){
for(i = 0;i < 10;i++){
if(histogram[a[i]] > 0){
printf("*\t");
--histogram[a[i]];
}
else printf(" \t");
}
printf("\n");
}
}
您好！请问您第二个题的答案有吗？我还是没想出来，能不能给个代码，另外把关键的地方给注释一下好吗？谢谢！
第二个题是难了点。不过所用到的知识到目前为止都讲过。本书不会给出参考答案的。 SICP也不给答案，算法导论也不给答案，但有人自己做了整套答案公开在网上， 有人建了邮件列表，专门讨论习题的答案。 我也想看到这样的结果。何况我的题比他们的题简单多了，我更没理由给答案了。
#include <stdio.h>
int list[100]={1};
int num ;
void input() {
printf("请输入第数列,以0结束\n");
num = -1 ;
do{
num ++ ;
scanf("%d",&list[ num ] );
}
while(list[num]);
num -- ;
}
void printfList() {
int i;
for( i = 0 ; i <= num ; i ++ ) {
printf("%d ", list[ i ] );
}
printf("\n");
}
void swap( int a , int b ) {
int temp = list[ b ] ;
list[ b ] = list[ a ] ;
list[ a ] = temp ;
}
void perm( int k ) {
int i ;
if( k == num ){
printfList();
return ;
}
for( i = k ; i <= num ; i ++ ){
swap( i , k );
perm( k + 1 );
swap( i , k );
}
}
main() {
input();
perm( 0 );
}
这个不是我做的。。但确实可以实现这个功能。。宋老师，您写的书很好，每个知识点讲解得精辟。题目精炼，我是第一次看到这么好的书。对我的C语言学习，给以极大的帮助。在此谢谢您无私的奉献！ 在直方图＞习题2中我发现了一个小小的错误，就是题目给出的程序结果中有7个排列，其中最后一个是多余的。
多谢指出！
Leave the smart & hard question to smart dude. I need to learn some basic knowledge firstly in order to find a decent job. I hope someday I can get the answer of No.2. No doubt there: Song is a smart guy!
第二题：M N的排列：
#include <stdio.h>
#define N 4
#define M 2
int a[N] = {1, 2, 3, 4};
void print_seq()
{
int i;
for(i = 0; i < M; i++)
printf("%d ", a[i]);
printf("\n");
}
void exchange(int i, int j)
{
int tmp;
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
void list_seq(int start)
{
if(start == M)
{
print_seq();
return;
}
int i;
for(i = start; i < N; i++){
exchange(start, i);
list_seq(start + 1);
exchange(i, start);
}
}
int main(void)
{
list_seq(0);
}M N 组合
#include <stdio.h>
#define N 4
#define M 2
int a[N] = {1, 2, 3, 4};
void print_seq()
{
int i;
for(i = 0; i < M; i++)
printf("%d ", a[i]);
printf("\n");
}
void exchange(int i, int j)
{
int tmp;
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
void list_seq(int start, int min)//min:当前的最小下标, start:当前M的第几个
{
if(start == M)
{
print_seq();
return;
}
int i;
for(i = min; i <= N - M + start; i++){
exchange(start, i);
list_seq(start + 1, i + 1);
exchange(i, start);
}
}
int main(void)
{
list_seq(0, 0);
}#include <stdio.h>
#define N 4
int s[] = {1, 2, 3, 4};
void swap(int a, int b)
{
int temp = s[a];
s[a] = s[b];
s[b] = temp;
}
void perm(int k)
{
int i;
int j = N - 1;
if (k == j) {
for (i = 0; i <= j; i++)
printf("%d\t",s[i]);
printf("\n");
} else {
for (i=k; i <= j; i++)
{
swap (k, i);
perm (k+1);
swap (k, i);
}
}
}
int main()
{
perm(0);
return 0;
} 原来 M 真的是前 M 个的意思？ 宋老师，麻烦确认一下，在正文里明确说明 M 是前 N 个还是任取。
学过排列、组合的都知道“N个里面取M个”是什么意思。而“具备高中的数学基础”是本书的prerequisite，前言里面说得很清楚。
第一题 ：
分享一下我做的
一开始把 printf(" ");打印一个空格给忘写了
导致每次都是0的个数最多 ，然后依次减少，
弄的我郁闷了半天，
#include <time.h>;
#include <stdio.h>
#include <stdlib.h>
#define N 100
int a[N];
void gen_random(int width)
{
int i;
srand(time(NULL));
for(i=0;i<N;i++)
{
a[i]=rand()%width;
}
}
int main()
{
int i,histogram[10]={0};
int b=0,j;
gen_random(10);
for(i=0;i<N;i++)
{
histogram[a[i]]++;
}
b=histogram[0];
for(i=0;i<(10-1);i++)
{
if(histogram[i+1]>b)
{
b=histogram[i+1];
}
}
printf("0123456789 \n\n");
for(i=1;i<=b;i++)
{
for(j=0;j<10;j++)
{
if(histogram[j]!=0)
{
histogram[j]--;
printf("*");
}
else
{
printf(" ");
}
}
printf("\n");
}
return 0;
}
哎 看了第二题的代码 感觉自己废
这是我做的第一题，请多多指教
#include <stdio.h>
#include <stdlib.h>
#define N 20
int a[N];
void gen_random(int upper_bound)
{
int i;
srand(time(NULL));
for (i = 0; i < N; i++)
a[i] = rand() % upper_bound;
}
int main(void)
{
int i , j , k , histogram[10] = {0};
gen_random(10);
for (i = 0; i < N; i++)
histogram[a[i]]++;
for (i = 0; i < 10; i++)
printf("%d ",i);
printf("\n");
for (i = 0; i < N; i++)
{
for ( k = 0; k < 10; k++)
{
if ( histogram[k] > i )
{
j = 1;
break;
}
}
if ( j == 1)
{
for ( k = 0; k < 10; k++)
{
if ( histogram[k] > i)
printf("* ");
else
printf(" ");
}
printf("\n");
j = 0;
}
}
return 0;
}
第一题：
写完后，发现没有检测 a[]的最大数值
参考了王文箫兄的最大数值检测语句。
#include <stdio.h>
#include <stdlib.h>
#define N 20
int a[N];
void gen_random(int upper_bound)
{
int i;
for (i = 0; i < N; i++)
a[i] = rand() % upper_bound;
}
int main(void)
{
int i,x,histogram[10] = {0};
gen_random(10);
for (i = 0; i < N; i++)
++histogram[a[i]];
for (i = 0; i < 10; i++)
printf ("%d ",i);
printf ("\n");
int maxa = histogram[0];
for (i =1; i < 10-1; i++)
if (maxa < histogram[i])
maxa = histogram[i];
for (x = 0; x < maxa; x++) {
for (i = 0; i < 10; i++) {
if (histogram[i] > 0) {
printf ("* ");
histogram[i]--;
}
else
printf (" ");
}
printf ("\n");
}
return 0;
}
第一题，动手操作最能让自己去解决问题
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 20
int a[N];
void get_rand(int upper)
{
int i;
//srand(time(NULL));
for (i=0; i<N; i++)
{
a[i] = rand()%upper;
}
}
int main(void)
{
get_rand(10);
int i,j,max = 0,arrCount[10] = {0};
for (i=0; i<N; i++)
{
arrCount[a[i]]++;
}
for (i=0; i<10; i++)
{
printf("%d\t", i);
if (arrCount[i] > max)
{
max = arrCount[i];
}
}
printf("\n\n");
for (i=0; i<max; i++)
{
for (j=0; j<10; j++)
{
if (arrCount[j] > 0)
{
printf("*\t");
arrCount[j]--;
}
else
{ printf(" \t");
}
}
printf("\n");
}
return 0;
}#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int i, j, k, m, count = 0, a[20], howmany[10] = {0};
for (i = 0; i < 20; ++i) {
a[i] = rand() % 10;
howmany[a[i]]++;
}
for (j = 0; j < 10; j++) {
printf ("%d\t", j);
}
printf ("\n");
printf ("\n");
for (k = 0; k < 20 && count < 20; k++) {
for (m = 0; m < 10; m++) {
if (howmany[m]) {
printf ("*\t");
howmany[m]--;
count++;
}
else
printf ("\t");
}
printf ("\n");
}
printf ("\n");
return 0;
}
第一题
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define N 20
int main(void)
{
int i,j,k,cnt;
int max=0, loact=0;
int b[10]={0};
srand(time(NULL));
for(i=0;i<N;i++)
{
b[ (rand()%10) ]++;
}
for(j=0; j<10; j++)
{
printf("%d ",j);
if(b[j]>max)
{
max=b[j];
loact=j;
}
}
printf("\n");
for(cnt=0; cnt<=max; cnt++)
{
for(k=0; k<10; k++)
{
if(b[k])
{
printf("* ");
b[k]--;
}
else
{
printf(" ");
}
}
printf("\n");
}
return 0;
}
只会第一题..
#include <stdio.h>
#include <stdlib.h>
#define N 20
int a[N];
void gen_random(int upper_bound)
{
int i;
for (i = 0; i < N; i++)
a[i] = rand() % upper_bound;
}
int howmany(int value)
{
int count = 0, i;
for (i = 0; i < N; i++)
if (a[i] == value)
++count;
return count;
}
int main(void)
{
int j ,i, histogram[10] = {0};
gen_random(10);
for (i = 0; i < N; i++)
histogram[a[i]]++;
for(i = 0; i < 10; i++)
{
printf("%d ",i);
}
printf("\n");
for (i = 0; i < N; i++)
{
for(j = 0; j < 10; j++)
{
if(histogram[j] > 0)
{
printf("* ");
histogram[j]--;
}
else
{
printf(" ");
}
}
printf("\n");
}
}
建议作者将排列组合这道算法题加星号吧。排列组合的确是高中数学知识，不过求解的递归算法对初学者来说真的很难。
// 排列
#include <stdio.h>
#define LEN 3
#define TOKEN 2
void swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void perm(int perm_arr[], // the array to process
int perm_ind, // the indicator of the process
int length_arr) // the length of the perm_arr
{
int i;
if (perm_ind == length_arr)
{
for (i = 0; i < length_arr; i++)
printf("%d\t", perm_arr[i]);
printf("\n");
}
else
{
for (i = perm_ind; i < length_arr; i++)
{
swap(&perm_arr[i], &perm_arr[perm_ind]);
perm(perm_arr, perm_ind + 1, length_arr);
swap(&perm_arr[i], &perm_arr[perm_ind]);
}
}
}
void perm_m(int array[], int m)
{
perm(array, 0, m);
}
void newline()
{
printf("\n");
}
int main(void)
{
int array[LEN] = {1, 2, 3};
perm(array, 0, LEN); // 第一个问题
newline();
perm_m(array, TOKEN); // 第二个问题
return 0;
}
// 组合
#include <stdio.h>
#define LEN 5
#define TOKEN 2
void combination(int a[], int len_ori, int len_req, int m, int b[])
{
int i, j;
for (i = len_ori; i >= len_req; i--)
{
b[len_req-1] = i-1;
if (len_req == 1)
{
for (j = m-1; j >= 0; j--)
printf("%d\t", a[b[j]]);
printf("\n");
}
else
{
combination(a, i-1, len_req-1, m, b);
}
}
}
int main(void)
{
int a[LEN] = {1, 2, 3, 4, 5};
int b[TOKEN];
combination(a, LEN, TOKEN, TOKEN, b); // 第三个问题
return 0;
}大家能不能帮解释下：在求排列时,为什么是swap>perm>swap? 后面一个swap是什么作用啊？ 我感觉好像对排列来说没什么影响啊！
后面一个swap是还原数组的排序。
bin.kou bin.kou@accenture.com
2009-10-26 22:55:29
#include <stdio.h>
#define N 4
int s[] = {1, 2, 3, 4};
void swap(int a, int b)
{
int temp = s[a];
s[a] = s[b];
s[b] = temp;
}
void perm(int k)
{
int i;
int j = N - 1;
if (k == j) {
for (i = 0; i <= j; i++)
printf("%d\t",s[i]);
printf("\n");
} else {
for (i=k; i <= j; i++)
{
swap (k, i);
perm (k+1);
swap (k, i);
}
}
}
int main()
{
perm(0);
return 0;
}
佩服，程序的思路异常清晰，化繁为简，虽然一行注释都没有，但一下就看懂了如果您有建设性意见，哪怕只是纠正一个错别字，也请不吝赐教，您留下的姓名和email将会出现在本书前言的致谢中。再次感谢您的宝贵意见！