C语言求解欧拉函数和本原根

Python030

C语言求解欧拉函数和本原根,第1张

#include <stdio.h>

int eulerFunc(int n, int* num_out) {

int i, j, cnt = 0

num_out[cnt++] = 1

for (i = 2 i <= n ++i) {

for (j = 2 j <= i ++j) {

if (i % j == 0 && n % j == 0) {

break

}

}

if (j > i) {

num_out[cnt++] = i

}

}

return cnt

}

int main(void) {

int n, num[10], y, i

scanf("%d", &n)

y = eulerFunc(n, num)

for (i = 0 i < y ++i) {

printf("%d ", num[i])

}

printf("\n%d", y)

return 0

}

截图亲，要代码高亮的截图亲。。。

ps 关于 c[] 怎么在主函数使用，

要么用函数返回，

要么主函数里弄个cz[]，在c[]的最后一步把结果存进cz[]，虽然很ugly，但是可以用。。。以后不要这么写。。。

这个东西用到赫夫曼树。需要你来画图，我这里说明一下。

树你知道吧，你给这8个字符8个结点（画圈，里面写概率）。然后找到其中最小的两个（0.03和0.05),作为叶子结点，放在树的最下面，然后得到一个新的结点作为这两个叶子的父结点，画个圈，里面的概率是0.08。然后用这个0.08代替0.03和0.05，那么只剩下7个了。接着再找最小的两个概率，重复这样的步骤，最终得到一棵树。跟结点的概率为1。然后你给所有结点与结点之间的连线上做标记，方向向左的标记0，向右的标记1。那么对于8个叶子结点，依次从上往下可以分别得到一个编码（由0和1组成），就是赫夫曼编码了。

这个是数据结构，最最重要的，下面有关于赫夫曼树的代码（和你的题目不是完全一样，仅供参考。

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<malloc.h>

#define LEN 8

#define MAXLEAF 8 // 最大叶子结点数目

#define MAXNODE (MAXLEAF*2)-1

typedef float ElemType

typedef struct /* this structure stores the information of code */

{

int start /* 存放编码的起始位置右至左（高位至低位）*/

int bit[LEN]/* 存放 huffman编码 */

}HCode

typedef HCode HuffCode[MAXLEAF]

typedef struct /* huffman tree结点的结构 */

{

int parent

int LChild

int RChild

ElemType weight

}HNode

typedef HNode Huffman[MAXLEAF*2-1]

void createHuffmanTree(Huffman h,int leaves,ElemType *weight)

{

int i,j

for(i=0i<leaves*2-1i++)/* 初始化huffman tree */

{

(h+i)->parent=-1

(h+i)->LChild=-1

(h+i)->RChild=-1

(h+i)->weight=0

}

for(i=0i<leavesi++)/* 给叶子赋权重 */

{

(h+i)->weight=*(weight+i)

}

/* 上一个循环叶子已经带权,下面这个循环用来生成新根

* 新根数量为n-1

*/

for(i=0i<leaves-1i++)

{

ElemType m1, m2

int m1_pos, m2_pos

m1=m2=65536/* m1存放最小的权值m2存放次小的权值 */

m1_pos=m2_pos=0/* m1存放最小的权值对应下标m2存放次小的权值对应下标*/

for(j=0j<leaves+ij++)

{

if((h+j)->weight<m1&&(h+j)->parent==-1)

{

m2=m1

m1=(h+j)->weight

m2_pos=m1_pos

m1_pos=j

}

else if((h+j)->weight<m2&&(h+j)->parent==-1)

{

m2=(h+j)->weight

m2_pos=j

}

}

(h+leaves+i)->parent=-1 // 生成新根，无双亲-1

(h+leaves+i)->LChild=m1_pos // 新根左孩子在数组中的下标

(h+leaves+i)->RChild=m2_pos // 新根右孩子在数组中的下标

(h+m1_pos)->parent=leaves+i // 原根的父亲位置

(h+m2_pos)->parent=leaves+i // 原根的父亲位置

(h+leaves+i)->weight=m2+m1

}

}

void huffmancode(Huffman h,HuffCode code,int leaves)

{

int i,j,p,c

HCode hf

/*从叶子结点开始向上回溯 从而计算出huffman code */

for(i=0i<leavesi++)

{

c=i

p=h[i].parent

hf.start=LEN-1

while(p!=-1)

{

if(h[p].LChild==c)

{

hf.bit[hf.start]=0

}

else

{

hf.bit[hf.start]=1

}

--hf.start

c=p

p=h[c].parent

}

for(j=hf.start+1j<LENj++)

{

code[i].bit[j]=hf.bit[j]

}

code[i].start=hf.start+1

}

}

void printhuffmantree(Huffman h,int leaves)

{

int i

for(i=0i<leaves*2-1i++)

{

printf("weight=%-3.2f",h[i].weight)

printf("parent=%-3d",h[i].parent)

printf("LChild=%-3d",h[i].LChild)

printf("RChild=%-3d\n",h[i].RChild)

}

}

void printhuffcode(HuffCode hcode,char characters[])

{

int i,j

for(i=0i<strlen(characters)i++)

{

printf("%c的huffman编码:",characters[i])

for(j=hcode[i].startj<LENj++)

{

printf("%d",hcode[i].bit[j])

}

printf("\n")

}

}

int main(void)

{

Huffman h

HuffCode hcode

char characters[]={"abcdef"} /* 待编码的字符 */

ElemType weights[]={0.3,0.7,0.4,0.5,0.9,0.1}/* 字符出现的频率 */

createHuffmanTree(h,strlen(characters),weights)

printhuffmantree(h,strlen(characters))

huffmancode(h,hcode,sizeof(characters))

printhuffcode(hcode,characters)

system("pause")

return 0

}