来自 编程 2019-09-28 17:06 的文章
当前位置: 澳门三合彩票 > 编程 > 正文

个别是插入成分的个数、以及须求打字与印刷的

05-树7:堆中的路径

05-树9 Huffman Codes(30 分)

In 1953, David A. Huffman published his paper "A Method for the Construction of Minimum-Redundancy Codes", and hence printed his name in the history of computer science. As a professor who gives the final exam problem on Huffman codes, I am encountering a big problem: the Huffman codes are NOT unique. For example, given a string "aaaxuaxz", we can observe that the frequencies of the characters 'a', 'x', 'u' and 'z' are 4, 2, 1 and 1, respectively. We may either encode the symbols as {'a'=0, 'x'=10, 'u'=110, 'z'=111}, or in another way as {'a'=1, 'x'=01, 'u'=001, 'z'=000}, both compress the string into 14 bits. Another set of code can be given as {'a'=0, 'x'=11, 'u'=100, 'z'=101}, but {'a'=0, 'x'=01, 'u'=011, 'z'=001} is NOT correct since "aaaxuaxz" and "aazuaxax" can both be decoded from the code 00001011001001. The students are submitting all kinds of codes, and I need a computer program to help me determine which ones are correct and which ones are not.

Description:

将一系列给定数字插入一个初始为空的小顶堆H[]。随后对任意给定的下标i,打印从H[i]到根结点的路径。

Input Specification:

Each input file contains one test case. For each case, the first line gives an integer N (2≤N≤63), then followed by a line that contains all the N distinct characters and their frequencies in the following format:

 

c[1] f[1] c[2] f[2] ... c[N] f[N]

where c[i] is a character chosen from {'0' - '9', 'a' - 'z', 'A' - 'Z', '_'}, and f[i] is the frequency of c[i] and is an integer no more than 1000. The next line gives a positive integer M (≤1000), then followed by M student submissions. Each student submission consists of Nlines, each in the format:

c[i] code[i]

where c[i] is the i澳门三合彩票,-th character and code[i] is an non-empty string of no more than 63 '0's and '1's.

Input:

每组测试第1行包含2个正整数N和M,分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。

Output Specification:

For each test case, print in each line either "Yes" if the student's submission is correct, or "No" if not.

Note: The optimal solution is not necessarily generated by Huffman algorithm. Any prefix code with code length being optimal is considered correct.

Output:

对输入中给出的每个下标i,在一行中输出从H[i]到根结点的路径上的数据。数字间以1个空格分隔,行末不得有多余空格。

Sample Input:

7
A 1 B 1 C 1 D 3 E 3 F 6 G 6
4
A 00000
B 00001
C 0001
D 001
E 01
F 10
G 11
A 01010
B 01011
C 0100
D 011
E 10
F 11
G 00
A 000
B 001
C 010
D 011
E 100
F 101
G 110
A 00000
B 00001
C 0001
D 001
E 00
F 10
G 11
SampleInput:

5 3
46 23 26 24 10
5 4 3

Sample Output:

Yes
Yes
No
No

这个程序我花了不少时间,改改,找错误,放弃,重写。只能 说细节很多,感觉每个程序 都不是那么简单,需要自己 默默地付出许多。

澳门三合彩票 1澳门三合彩票 2

  1 #include<iostream>
  2 #include<vector>
  3 using namespace std;
  4 #define maxsize 64
  5 struct node{
  6 int weight=-1;
  7 node* l=NULL;
  8 node* r=NULL;
  9 };
 10 using haffmantree=node;
 11 vector<node> Minheap;
 12 vector<int> no;
 13 int size,flag=1;
 14 void Createheap(int N){
 15 Minheap.resize(N+1);
 16 node n; Minheap[0]=n;
 17 size=0;
 18 }
 19 void Insert(node n){
 20   int i=++size;
 21   for(;Minheap[i/2].weight>n.weight;i/=2)
 22   Minheap[i]=Minheap[i/2];
 23   Minheap[i]=n;
 24 }
 25 void ReadData(int N){
 26 for(int i=1;i<=N;i++){
 27 string str; int num;
 28 cin>>str>>num;
 29 no.push_back(num);
 30 node n;
 31 n.weight=num;
 32 Insert(n);
 33 }
 34 }
 35 node* Delete(){
 36 node* n=new node();
 37 n->l=Minheap[1].l;
 38 n->r=Minheap[1].r;
 39 n->weight=Minheap[1].weight;
 40 node temp=Minheap[size--];
 41 int parent,child;
 42 for(parent=1;parent*2<=size;parent=child){
 43 child=2*parent;
 44 if(child!=size&&Minheap[child+1].weight<Minheap[child].weight)
 45 ++child;
 46 if(temp.weight<=Minheap[child].weight) break;
 47 else 
 48 Minheap[parent]=Minheap[child];
 49 }
 50 Minheap[parent]=temp;
 51 return n;
 52 }
 53 haffmantree huffman(int N){
 54     node T;
 55 for(int i=1;i<N;i++){
 56 node n;
 57 n.l=Delete();
 58 n.r=Delete();
 59 n.weight=n.l->weight+n.r->weight;
 60 Insert(n); 
 61 } 
 62 T=*Delete();
 63 return T;
 64 }
 65 int WPL(haffmantree T,int depth)
 66 { 
 67 if(T.l==NULL&&T.r==NULL) return depth*(T.weight);
 68 else return WPL(*(T.l),depth+1)+WPL(*(T.r),depth+1);
 69 }
 70 void judge(haffmantree* h,string code){
 71 for(int i=0;i<code.length();i++){
 72 if(code[i]=='0'){
 73 if(h->l==NULL){
 74 node* nod=new node();
 75 h->l=nod;
 76 }
 77 else if(h->l->weight>0)
 78      flag=0;
 79 h=h->l;
 80 }
 81 else if(code[i]=='1'){
 82 if(h->r==NULL){
 83 node* nod=new node();
 84 h->r=nod;
 85 }else if(h->r->weight>0)
 86      flag=0;
 87     h=h->r;
 88 }
 89 }
 90 if(h->r==NULL&&h->l==NULL)
 91 h->weight=1;
 92 else flag=0;
 93 }
 94 int main(){
 95 int N; cin>>N;
 96 Createheap(N);
 97 ReadData(N);
 98 haffmantree T=huffman(N);
 99 int wpl=WPL(T,0);
100 int M; cin>>M;
101 for(int i=1;i<=M;i++){
102 int len=0; haffmantree* h=new node();
103 for(int j=0;j<N;j++){
104 string str,code;
105 cin>>str>>code;
106 judge(h,code);
107 len+=no[j]*code.length();
108 }
109 if(len!=wpl) flag=0;
110 if(flag==1) cout<<"Yes"<<endl;
111 else cout<<"No"<<endl;
112 flag=1;
113 }
114     return 0; 
115 } 

View Code

 

SampleOutput:

24 23 10
46 23 10
26 10

Codes:
//#define LOCAL#include <cstdio>#define M 1010#define S -10010int i, cnt, A[M] = {S};void insert {    for(i=++cnt; A[i/2]>a; i/=2) A[i] = A[i/2];    A[i] = a;}int main(){    #ifdef LOCAL        freopen("E:\Temp\input.txt", "r", stdin);        freopen("E:\Temp\output.txt", "w", stdout);    #endif    int a, n, m;    scanf("%d%d", &n, &m);    while { scanf("%d", &a); insert; }    while {        scanf("%d", &a);        printf("%d", A[a]); a /= 2;        while { printf(" %d", A[a]); a /= 2; }         printf;     }    return 0;}
05-树8:File Transfer.
Description:

We have a network of computers and a list of bi-directional connections. Each of these connections allows a file transfer from one computer to another. Is it possible to send a file from any computer on the network to any other?

Input:

Each input file contains one test case. For each test case, the first line contains N, the total number of computers in a network. Each computer in the network is then represented by a positive integer between 1 and N. Then in the following lines, the input is given in the format: I c1 c2 where I stands for inputting a connection between c1 and c2; or C c1 c2 where C stands for checking if it is possible to transfer files between c1 and c2; or S where S stands for stopping this case.

Output:

For each C case, print in one line the word "yes" or "no" if it is possible or impossible to transfer files between c1 and c2, respectively. At the end of each case, print in one line "The network is connected." if there is a path between any pair of computers; or "There are k components." where k is the number of connected components in this network.

SampleInput1:

5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
S

本文由澳门三合彩票发布于编程,转载请注明出处:个别是插入成分的个数、以及须求打字与印刷的

关键词: