рдЕрднреНрдпрд╛рд╕рдХреНрд░рдо рд╕реБрд░реВ рд╣реЛрдгреНрдпрд╛рдкреВрд░реНрд╡реА
рд╣рдлрдорди рдХреЛрдбрд┐рдВрдЧ рд╣рд╛ рдбреЗрдЯрд╛ рдХреЙрдореНрдкреНрд░реЗрд╢рди рдЕрд▓реНрдЧреЛрд░рд┐рджрдо рдЖрд╣реЗ рдЬреЛ рдлрд╛рдЗрд▓ рдХреЙрдореНрдкреНрд░реЗрд╢рдирдЪреА рдореВрд▓рднреВрдд рдХрд▓реНрдкрдирд╛ рддрдпрд╛рд░ рдХрд░рддреЛ. рдпрд╛ рд▓реЗрдЦрд╛рдд, рдЖрдореНрд╣реА рдирд┐рд╢реНрдЪрд┐рдд рдЖрдгрд┐ рдкрд░рд┐рд╡рд░реНрддрдиреАрдп рд▓рд╛рдВрдмреАрдЪреЗ рдПрдиреНрдХреЛрдбрд┐рдВрдЧ, рдЕрджреНрд╡рд┐рддреАрдпрдкрдгреЗ рдбреАрдХреЛрдб рдХрд░рдгреНрдпрд╛рдпреЛрдЧреНрдп рдХреЛрдб, рдЙрдкрд╕рд░реНрдЧ рдирд┐рдпрдо рдЖрдгрд┐ рд╣рдлрдорди рдЯреНрд░реА рддрдпрд╛рд░ рдХрд░рдгреНрдпрд╛рдмрджреНрджрд▓ рдмреЛрд▓реВ.
рдЖрдореНрд╣рд╛рд▓рд╛ рдорд╛рд╣рд┐рдд рдЖрд╣реЗ рдХреА рдкреНрд░рддреНрдпреЗрдХ рд╡рд░реНрдг 0 рдЖрдгрд┐ 1 рдЪреНрдпрд╛ рдХреНрд░рдорд╛рдиреЗ рд╕рдВрдЧреНрд░рд╣рд┐рдд рдХреЗрд▓рд╛ рдЬрд╛рддреЛ рдЖрдгрд┐ 8 рдмрд┐рдЯ рдШреЗрддреЛ. рдпрд╛рд▓рд╛ рдирд┐рд╢реНрдЪрд┐рдд рд▓рд╛рдВрдмреАрдЪреЗ рдПрдиреНрдХреЛрдбрд┐рдВрдЧ рдореНрд╣рдгрддрд╛рдд рдХрд╛рд░рдг рдкреНрд░рддреНрдпреЗрдХ рд╡рд░реНрдг рд╕рдВрдЪрдпрд┐рдд рдХрд░рдгреНрдпрд╛рд╕рд╛рдареА рд╕рдорд╛рди рдирд┐рд╢реНрдЪрд┐рдд рдмрд┐рдЯреНрд╕ рд╡рд╛рдкрд░рддреЛ.
рд╕рдордЬрд╛ рдЖрдореНрд╣рд╛рд▓рд╛ рдордЬрдХреВрд░ рджрд┐рд▓рд╛ рдЖрд╣реЗ. рдПрдХрд▓ рдЕрдХреНрд╖рд░ рд╕рд╛рдард╡рдгреНрдпрд╛рд╕рд╛рдареА рдЖрд╡рд╢реНрдпрдХ рдЕрд╕рд▓реЗрд▓реА рдЬрд╛рдЧрд╛ рдЖрдкрдг рдХрд╢реА рдХрдореА рдХрд░реВ рд╢рдХрддреЛ?
рдореБрдЦреНрдп рдХрд▓реНрдкрдирд╛ рд╡реНрд╣реЗрд░рд┐рдПрдмрд▓ рд▓рд╛рдВрдмреА рдПрдиреНрдХреЛрдбрд┐рдВрдЧ рдЖрд╣реЗ. рдЖрдореНрд╣реА рд╣реЗ рддрдереНрдп рд╡рд╛рдкрд░реВ рд╢рдХрддреЛ рдХреА рдордЬрдХреВрд░рд╛рддреАрд▓ рдХрд╛рд╣реА рд╡рд░реНрдг рдЗрддрд░рд╛рдВрдкреЗрдХреНрд╖рд╛ рдЬрд╛рд╕реНрдд рд╡реЗрд│рд╛ рдЖрдврд│рддрд╛рдд (
рдмрд┐рдЯреНрд╕рдЪрд╛ рдХреНрд░рдо рдЬрд╛рдгреВрди рдШреЗрдКрди рддреЗ рдЕрд╕реНрдкрд╖реНрдЯрдкрдгреЗ рдХрд╕реЗ рдбреАрдХреЛрдб рдХрд░рд╛рдпрдЪреЗ?
рдУрд│ рд╡рд┐рдЪрд╛рд░рд╛рдд рдШреНрдпрд╛ "рдЕрдмрдХрдбрдм". рдпрд╛рдд 8 рд╡рд░реНрдг рдЖрд╣реЗрдд рдЖрдгрд┐ рдирд┐рд╢реНрдЪрд┐рдд рд▓рд╛рдВрдмреАрдЪреЗ рдПрдиреНрдХреЛрдбрд┐рдВрдЧ рдХрд░рддрд╛рдирд╛, рддреЗ рд╕рдВрдЪрдпрд┐рдд рдХрд░рдгреНрдпрд╛рд╕рд╛рдареА 64 рдмрд┐рдЯреНрд╕рдЪреА рдЖрд╡рд╢реНрдпрдХрддрд╛ рдЕрд╕реЗрд▓. рдЪрд┐рдиреНрд╣ рд╡рд╛рд░рдВрд╡рд╛рд░рддрд╛ рд▓рдХреНрд╖рд╛рдд рдареЗрд╡рд╛ "a", "b", "c" ╨╕ "рдбреА" рдЕрдиреБрдХреНрд░рдореЗ 4, 2, 1, 1 рдмрд░реЛрдмрд░ рдЖрд╣реЗ. рдЪрд▓рд╛ рдХрд▓реНрдкрдирд╛ рдХрд░рдгреНрдпрд╛рдЪрд╛ рдкреНрд░рдпрддреНрди рдХрд░реВрдпрд╛ "рдЕрдмрдХрдбрдм" рдХрдореА рдмрд┐рдЯ, рд╡рд╕реНрддреБрд╕реНрдерд┐рддреА рд╡рд╛рдкрд░реВрди "рддреЗ" рдкреЗрдХреНрд╖рд╛ рдЕрдзрд┐рдХ рд╡рд╛рд░рдВрд╡рд╛рд░ рдЙрджреНрднрд╡рддреЗ "рдм"рдЖрдгрд┐ "рдм" рдкреЗрдХреНрд╖рд╛ рдЕрдзрд┐рдХ рд╡рд╛рд░рдВрд╡рд╛рд░ рдЙрджреНрднрд╡рддреЗ "c" ╨╕ "рдбреА". рдЪрд▓рд╛ рдХреЛрдбрд┐рдВрдЧ рдХрд░реВрди рд╕реБрд░реБрд╡рд╛рдд рдХрд░реВрдпрд╛ "рддреЗ" рдПрдХ рдмрд┐рдЯ 0 рдЪреНрдпрд╛ рдмрд░реЛрдмрд░реАрдиреЗ, "рдм" рдЖрдореНрд╣реА рджреЛрди-рдмрд┐рдЯ рдХреЛрдб 11 рдирд┐рдпреБрдХреНрдд рдХрд░реВ, рдЖрдгрд┐ рддреАрди рдмрд┐рдЯ 100 рдЖрдгрд┐ 011 рд╡рд╛рдкрд░реВрди рдЖрдореНрд╣реА рдПрдиреНрдХреЛрдб рдХрд░реВ "c" ╨╕ "рдбреА".
рдкрд░рд┐рдгрд╛рдореА, рдЖрдореНрд╣рд╛рд▓рд╛ рдорд┐рд│реЗрд▓:
a
0
b
11
c
100
d
011
рддрд░ рдУрд│ "рдЕрдмрдХрдбрдм" рдореНрд╣рдгреВрди рдПрдиреНрдХреЛрдб рдХрд░реВ 00110100011011 (0|0|11|0|100|011|0|11)рд╡рд░реАрд▓ рдХреЛрдб рд╡рд╛рдкрд░реВрди. рддрдерд╛рдкрд┐, рдореБрдЦреНрдп рд╕рдорд╕реНрдпрд╛ рдбреАрдХреЛрдбрд┐рдВрдЧрдордзреНрдпреЗ рдЕрд╕реЗрд▓. рдЬреЗрд╡реНрд╣рд╛ рдЖрдкрдг рд╕реНрдЯреНрд░рд┐рдВрдЧ рдбреАрдХреЛрдб рдХрд░рдгреНрдпрд╛рдЪрд╛ рдкреНрд░рдпрддреНрди рдХрд░рддреЛ 00110100011011, рдЖрдореНрд╣рд╛рд▓рд╛ рдПрдХ рд╕рдВрджрд┐рдЧреНрдз рдкрд░рд┐рдгрд╛рдо рдорд┐рд│рддреЛ, рдХрд╛рд░рдг рддреЗ рдЕрд╕реЗ рджрд░реНрд╢рд╡рд▓реЗ рдЬрд╛рдК рд╢рдХрддреЗ:
0|011|0|100|011|0|11 adacdab
0|0|11|0|100|0|11|011 aabacabd
0|011|0|100|0|11|0|11 adacabab
...
рдЖрдгрд┐ рдпрд╛рдкреНрд░рдорд╛рдгреЗ.
рд╣реА рд╕рдВрджрд┐рдЧреНрдзрддрд╛ рдЯрд╛рд│рдгреНрдпрд╛рд╕рд╛рдареА, рдЖрдореНрд╣реА рд╣реЗ рд╕реБрдирд┐рд╢реНрдЪрд┐рдд рдХреЗрд▓реЗ рдкрд╛рд╣рд┐рдЬреЗ рдХреА рдЖрдордЪреЗ рдПрдиреНрдХреЛрдбрд┐рдВрдЧ рдЕрд╢рд╛ рд╕рдВрдХрд▓реНрдкрдиреЗрдЪреЗ рд╕рдорд╛рдзрд╛рди рдХрд░рддреЗ рдЙрдкрд╕рд░реНрдЧ рдирд┐рдпрдо, рдЬреЗ рдпрд╛рдордзреВрди рд╕реВрдЪрд┐рдд рдХрд░рддреЗ рдХреА рдХреЛрдб рдХреЗрд╡рд│ рдПрдХрд╛ рдЕрджреНрд╡рд┐рддреАрдп рдорд╛рд░реНрдЧрд╛рдиреЗ рдбреАрдХреЛрдб рдХреЗрд▓реЗ рдЬрд╛рдК рд╢рдХрддрд╛рдд. рдЙрдкрд╕рд░реНрдЧ рдирд┐рдпрдо рд╣реЗ рд╕реБрдирд┐рд╢реНрдЪрд┐рдд рдХрд░рддреЛ рдХреА рдХреЛрдгрддрд╛рд╣реА рдХреЛрдб рджреБрд╕рд░реНтАНрдпрд╛рдЪрд╛ рдЙрдкрд╕рд░реНрдЧ рдирд╛рд╣реА. рдХреЛрдбрджреНрд╡рд╛рд░реЗ, рдЖрдордЪрд╛ рдЕрд░реНрде рдПрдЦрд╛рджреНрдпрд╛ рд╡рд┐рд╢рд┐рд╖реНрдЯ рд╡рд░реНрдгрд╛рдЪреЗ рдкреНрд░рддрд┐рдирд┐рдзрд┐рддреНрд╡ рдХрд░рдгреНрдпрд╛рд╕рд╛рдареА рд╡рд╛рдкрд░рд▓реНрдпрд╛ рдЬрд╛рдгрд╛рд░реНтАНрдпрд╛ рдмрд┐рдЯреНрд╕ рдЖрд╣реЗрдд. рд╡рд░реАрд▓ рдЙрджрд╛рд╣рд░рдгрд╛рдд 0 рдПрдХ рдЙрдкрд╕рд░реНрдЧ рдЖрд╣реЗ 011, рдЬреЗ рдЙрдкрд╕рд░реНрдЧ рдирд┐рдпрдорд╛рдЪреЗ рдЙрд▓реНрд▓рдВрдШрди рдХрд░рддреЗ. рддрд░, рдЬрд░ рдЖрдордЪреЗ рдХреЛрдб рдЙрдкрд╕рд░реНрдЧ рдирд┐рдпрдо рдкреВрд░реНрдг рдХрд░рддрд╛рдд, рддрд░ рдЖрдореНрд╣реА рдЕрдирдиреНрдпрдкрдгреЗ рдбреАрдХреЛрдб рдХрд░реВ рд╢рдХрддреЛ (рдЖрдгрд┐ рдЙрд▓рдЯ).
рдЪрд▓рд╛ рд╡рд░реАрд▓ рдЙрджрд╛рд╣рд░рдг рдкреБрдиреНрд╣рд╛ рдкрд╛рд╣реВ. рдпрд╛рд╡реЗрд│реА рдЖрдкрдг рдЪрд┐рдиреНрд╣рд╛рдВрд╕рд╛рдареА рдирд┐рдпреБрдХреНрдд рдХрд░реВ "a", "b", "c" ╨╕ "рдбреА" рдЙрдкрд╕рд░реНрдЧ рдирд┐рдпрдо рдкреВрд░реНрдг рдХрд░рдгрд╛рд░реЗ рдХреЛрдб.
a
0
b
10
c
110
d
111
рдпрд╛ рдПрдиреНрдХреЛрдбрд┐рдВрдЧрд╕рд╣, рд╕реНрдЯреНрд░рд┐рдВрдЧ "рдЕрдмрдХрдбрдм" рдореНрд╣рдгреВрди рдПрдиреНрдХреЛрдб рдХреЗрд▓реЗ рдЬрд╛рдИрд▓ 00100100011010 (0|0|10|0|100|011|0|10). рдкрдг 00100100011010 рдЖрдореНрд╣реА рдЖрдзреАрдЪ рдирд┐рдГрд╕рдВрджрд┐рдЧреНрдзрдкрдгреЗ рдбреАрдХреЛрдб рдХрд░рдгреНрдпрд╛рд╕ рдЖрдгрд┐ рдЖрдордЪреНрдпрд╛ рдореВрд│ рд╕реНрдЯреНрд░рд┐рдВрдЧрд╡рд░ рдкрд░рдд рдпреЗрдК рд╢рдХреВ "рдЕрдмрдХрдбрдм".
рд╣рдлрдорди рдХреЛрдбрд┐рдВрдЧ
рдЖрддрд╛ рдЖрдкрдг рд╡реНрд╣реЗрд░рд┐рдПрдмрд▓ рд▓рд╛рдВрдмреА рдПрдиреНрдХреЛрдбрд┐рдВрдЧ рдЖрдгрд┐ рдЙрдкрд╕рд░реНрдЧ рдирд┐рдпрдо рд╣рд╛рддрд╛рд│рд▓реЗ рдЖрд╣реЗ, рдЪрд▓рд╛ рд╣рдлрдорди рдПрдиреНрдХреЛрдбрд┐рдВрдЧрдмрджреНрджрд▓ рдмреЛрд▓реВрдпрд╛.
рдкрджреНрдзрдд рдмрд╛рдпрдирд░реА рдЭрд╛рдбрд╛рдВрдЪреНрдпрд╛ рдирд┐рд░реНрдорд┐рддреАрд╡рд░ рдЖрдзрд╛рд░рд┐рдд рдЖрд╣реЗ. рддреНрдпрд╛рдордзреНрдпреЗ, рдиреЛрдб рдПрдХрддрд░ рдЕрдВрддрд┐рдо рдХрд┐рдВрд╡рд╛ рдЕрдВрддрд░реНрдЧрдд рдЕрд╕реВ рд╢рдХрддреЛ. рд╕реБрд░реБрд╡рд╛рддреАрд▓рд╛, рд╕рд░реНрд╡ рдиреЛрдбреНрд╕ рдкрд╛рдиреЗ (рдЯрд░реНрдорд┐рдирд▓) рдорд╛рдирд▓реЗ рдЬрд╛рддрд╛рдд, рдЬреЗ рдЪрд┐рдиреНрд╣ рд╕реНрд╡рддрдГрдЪреЗ рдЖрдгрд┐ рддреНрдпрд╛рдЪреЗ рд╡рдЬрди (рдореНрд╣рдгрдЬреЗрдЪ рдШрдЯрдиреЗрдЪреА рд╡рд╛рд░рдВрд╡рд╛рд░рддрд╛) рджрд░реНрд╢рд╡рддрд╛рдд. рдЕрдВрддрд░реНрдЧрдд рдиреЛрдбреНрд╕рдордзреНрдпреЗ рд╡рд░реНрдгрд╛рдЪреЗ рд╡рдЬрди рдЕрд╕рддреЗ рдЖрдгрд┐ рддреЗ рджреЛрди рд╡рдВрд╢рдЬ рдиреЛрдбреНрд╕рдЪрд╛ рд╕рдВрджрд░реНрдн рдШреЗрддрд╛рдд. рд╕рд╛рдорд╛рдиреНрдп рдХрд░рд╛рд░рд╛рдиреБрд╕рд╛рд░, рдмрд┐рдЯ "0" рдЦрд╛рд▓реАрд▓ рдбрд╛рд╡реНрдпрд╛ рд╢рд╛рдЦреЗрдЪреЗ рдкреНрд░рддрд┐рдирд┐рдзрд┐рддреНрд╡ рдХрд░рддреЗ, рдЖрдгрд┐ "1" - рдЙрдЬрд╡реАрдХрдбреЗ. рдкреВрд░реНрдг рдЭрд╛рдбрд╛рдд N рдкрд╛рдиреЗ рдЖрдгрд┐ рдПрди-1 рдЕрдВрддрд░реНрдЧрдд рдиреЛрдбреНрд╕. рд╣рдлрдорди рдЯреНрд░реА рдмрдирд╡рддрд╛рдирд╛, рдЗрд╖реНрдЯрддрдо рд▓рд╛рдВрдмреАрдЪреЗ рдХреЛрдб рдорд┐рд│рд╡рд┐рдгреНрдпрд╛рд╕рд╛рдареА рди рд╡рд╛рдкрд░рд▓реЗрд▓реА рдЪрд┐рдиреНрд╣реЗ рдЯрд╛рдХреВрди рджреЗрдгреНрдпрд╛рдЪреА рд╢рд┐рдлрд╛рд░рд╕ рдХреЗрд▓реА рдЬрд╛рддреЗ.
рд╣рдлрдорди рдЯреНрд░реА рддрдпрд╛рд░ рдХрд░рдгреНрдпрд╛рд╕рд╛рдареА рдЖрдореНрд╣реА рдкреНрд░рд╛рдзрд╛рдиреНрдп рд░рд╛рдВрдЧ рд╡рд╛рдкрд░реВ, рдЬрд┐рдереЗ рд╕рд░реНрд╡рд╛рдд рдХрдореА рд╡рд╛рд░рдВрд╡рд╛рд░рддрд╛ рдЕрд╕рд▓реЗрд▓реНрдпрд╛ рдиреЛрдбрд▓рд╛ рд╕рд░реНрд╡реЛрдЪреНрдЪ рдкреНрд░рд╛рдзрд╛рдиреНрдп рджрд┐рд▓реЗ рдЬрд╛рдИрд▓. рдмрд╛рдВрдзрдХрд╛рдо рдкрд╛рдпрд▒реНрдпрд╛ рдЦрд╛рд▓реА рд╡рд░реНрдгрди рдХреЗрд▓реНрдпрд╛ рдЖрд╣реЗрдд:
- рдкреНрд░рддреНрдпреЗрдХ рд╡рд░реНрдгрд╛рд╕рд╛рдареА рд▓реАрдл рдиреЛрдб рддрдпрд╛рд░ рдХрд░рд╛ рдЖрдгрд┐ рддреНрдпрд╛рдВрдирд╛ рдкреНрд░рд╛рдзрд╛рдиреНрдп рд░рд╛рдВрдЧреЗрдд рдЬреЛрдбрд╛.
- рд░рд╛рдВрдЧреЗрдд рдПрдХрд╛рдкреЗрдХреНрд╖рд╛ рдЬрд╛рд╕реНрдд рд╢реАрдЯ рдЕрд╕рддрд╛рдирд╛, рдкреБрдвреАрд▓ рдЧреЛрд╖реНрдЯреА рдХрд░рд╛:
- рд░рд╛рдВрдЧреЗрддреВрди рд╕рд░реНрд╡реЛрдЪреНрдЪ рдкреНрд░рд╛рдзрд╛рдиреНрдп (рд╕рд░реНрд╡рд╛рдд рдХрдореА рд╡рд╛рд░рдВрд╡рд╛рд░рддрд╛) рдЕрд╕рд▓реЗрд▓реЗ рджреЛрди рдиреЛрдбреНрд╕ рдХрд╛рдврд╛;
- рдПрдХ рдирд╡реАрди рдЕрдВрддрд░реНрдЧрдд рдиреЛрдб рддрдпрд╛рд░ рдХрд░рд╛, рдЬрд┐рдереЗ рд╣реЗ рджреЛрди рдиреЛрдб рд▓рд╣рд╛рди рдЕрд╕рддреАрд▓ рдЖрдгрд┐ рдШрдЯрдирд╛рдВрдЪреА рд╡рд╛рд░рдВрд╡рд╛рд░рддрд╛ рдпрд╛ рджреЛрди рдиреЛрдбреНрд╕рдЪреНрдпрд╛ рдлреНрд░рд┐рдХреНрд╡реЗрдиреНрд╕реАрдЪреНрдпрд╛ рдмреЗрд░рдЬреЗрдЗрддрдХреА рдЕрд╕реЗрд▓.
- рдкреНрд░рд╛рдзрд╛рдиреНрдп рд░рд╛рдВрдЧреЗрдд рдирд╡реАрди рдиреЛрдб рдЬреЛрдбрд╛.
- рдлрдХреНрдд рдЙрд░реНрд╡рд░рд┐рдд рдиреЛрдб рд░реВрдЯ рдЕрд╕реЗрд▓ рдЖрдгрд┐ рдпрд╛рдореБрд│реЗ рдЭрд╛рдбрд╛рдЪреЗ рдмрд╛рдВрдзрдХрд╛рдо рдкреВрд░реНрдг рд╣реЛрдИрд▓.
рдХрд▓реНрдкрдирд╛ рдХрд░рд╛ рдХреА рдЖрдкрд▓реНрдпрд╛рдХрдбреЗ рдХрд╛рд╣реА рдордЬрдХреВрд░ рдЖрд╣реЗ рдЬреНрдпрд╛рдордзреНрдпреЗ рдлрдХреНрдд рд╡рд░реНрдг рдЖрд╣реЗрдд "рдЕ рдм рдХ рдб" ╨╕ "рдЖрдгрд┐", рдЖрдгрд┐ рддреНрдпрд╛рдВрдЪреНрдпрд╛ рдШрдЯрдирд╛ рд╡рд╛рд░рдВрд╡рд╛рд░рддрд╛ рдЕрдиреБрдХреНрд░рдореЗ 15, 7, 6, 6 рдЖрдгрд┐ 5 рдЖрд╣реЗрдд. рдЦрд╛рд▓реА рдЕрд▓реНрдЧреЛрд░рд┐рджрдордЪреНрдпрд╛ рдкрд╛рдпрд▒реНрдпрд╛ рдкреНрд░рддрд┐рдмрд┐рдВрдмрд┐рдд рдХрд░рдгрд╛рд░реА рдЙрджрд╛рд╣рд░рдгреЗ рдЖрд╣реЗрдд.
рд░реВрдЯрдкрд╛рд╕реВрди рдХреЛрдгрддреНрдпрд╛рд╣реА рдПрдВрдб рдиреЛрдбрдкрд░реНрдпрдВрддрдЪрд╛ рдорд╛рд░реНрдЧ рддреНрдпрд╛ рдПрдВрдб рдиреЛрдбрд╢реА рд╕рдВрдмрдВрдзрд┐рдд рдХреЕрд░реЗрдХреНрдЯрд░рд╢реА рд╕рдВрдмрдВрдзрд┐рдд рдЗрд╖реНрдЯрддрдо рдЙрдкрд╕рд░реНрдЧ рдХреЛрдб (рд╣рдлрдорди рдХреЛрдб рдореНрд╣рдгреВрдирд╣реА рдУрд│рдЦрд▓рд╛ рдЬрд╛рддреЛ) рд╕рдВрдЧреНрд░рд╣рд┐рдд рдХрд░реЗрд▓.
рд╣рдлрдорди рдЭрд╛рдб
рдЦрд╛рд▓реА рддреБрдореНрд╣рд╛рд▓рд╛ C++ рдЖрдгрд┐ Java рдордзреНрдпреЗ рд╣рдлрдорди рдХреЙрдореНрдкреНрд░реЗрд╢рди рдЕрд▓реНрдЧреЛрд░рд┐рджрдордЪреА рдЕрдВрдорд▓рдмрдЬрд╛рд╡рдгреА рдЖрдврд│реЗрд▓:
#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;
// A Tree node
struct Node
{
char ch;
int freq;
Node *left, *right;
};
// Function to allocate a new tree node
Node* getNode(char ch, int freq, Node* left, Node* right)
{
Node* node = new Node();
node->ch = ch;
node->freq = freq;
node->left = left;
node->right = right;
return node;
}
// Comparison object to be used to order the heap
struct comp
{
bool operator()(Node* l, Node* r)
{
// highest priority item has lowest frequency
return l->freq > r->freq;
}
};
// traverse the Huffman Tree and store Huffman Codes
// in a map.
void encode(Node* root, string str,
unordered_map<char, string> &huffmanCode)
{
if (root == nullptr)
return;
// found a leaf node
if (!root->left && !root->right) {
huffmanCode[root->ch] = str;
}
encode(root->left, str + "0", huffmanCode);
encode(root->right, str + "1", huffmanCode);
}
// traverse the Huffman Tree and decode the encoded string
void decode(Node* root, int &index, string str)
{
if (root == nullptr) {
return;
}
// found a leaf node
if (!root->left && !root->right)
{
cout << root->ch;
return;
}
index++;
if (str[index] =='0')
decode(root->left, index, str);
else
decode(root->right, index, str);
}
// Builds Huffman Tree and decode given input text
void buildHuffmanTree(string text)
{
// count frequency of appearance of each character
// and store it in a map
unordered_map<char, int> freq;
for (char ch: text) {
freq[ch]++;
}
// Create a priority queue to store live nodes of
// Huffman tree;
priority_queue<Node*, vector<Node*>, comp> pq;
// Create a leaf node for each character and add it
// to the priority queue.
for (auto pair: freq) {
pq.push(getNode(pair.first, pair.second, nullptr, nullptr));
}
// do till there is more than one node in the queue
while (pq.size() != 1)
{
// Remove the two nodes of highest priority
// (lowest frequency) from the queue
Node *left = pq.top(); pq.pop();
Node *right = pq.top(); pq.pop();
// Create a new internal node with these two nodes
// as children and with frequency equal to the sum
// of the two nodes' frequencies. Add the new node
// to the priority queue.
int sum = left->freq + right->freq;
pq.push(getNode('', sum, left, right));
}
// root stores pointer to root of Huffman Tree
Node* root = pq.top();
// traverse the Huffman Tree and store Huffman Codes
// in a map. Also prints them
unordered_map<char, string> huffmanCode;
encode(root, "", huffmanCode);
cout << "Huffman Codes are :n" << 'n';
for (auto pair: huffmanCode) {
cout << pair.first << " " << pair.second << 'n';
}
cout << "nOriginal string was :n" << text << 'n';
// print encoded string
string str = "";
for (char ch: text) {
str += huffmanCode[ch];
}
cout << "nEncoded string is :n" << str << 'n';
// traverse the Huffman Tree again and this time
// decode the encoded string
int index = -1;
cout << "nDecoded string is: n";
while (index < (int)str.size() - 2) {
decode(root, index, str);
}
}
// Huffman coding algorithm
int main()
{
string text = "Huffman coding is a data compression algorithm.";
buildHuffmanTree(text);
return 0;
}
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
// A Tree node
class Node
{
char ch;
int freq;
Node left = null, right = null;
Node(char ch, int freq)
{
this.ch = ch;
this.freq = freq;
}
public Node(char ch, int freq, Node left, Node right) {
this.ch = ch;
this.freq = freq;
this.left = left;
this.right = right;
}
};
class Huffman
{
// traverse the Huffman Tree and store Huffman Codes
// in a map.
public static void encode(Node root, String str,
Map<Character, String> huffmanCode)
{
if (root == null)
return;
// found a leaf node
if (root.left == null && root.right == null) {
huffmanCode.put(root.ch, str);
}
encode(root.left, str + "0", huffmanCode);
encode(root.right, str + "1", huffmanCode);
}
// traverse the Huffman Tree and decode the encoded string
public static int decode(Node root, int index, StringBuilder sb)
{
if (root == null)
return index;
// found a leaf node
if (root.left == null && root.right == null)
{
System.out.print(root.ch);
return index;
}
index++;
if (sb.charAt(index) == '0')
index = decode(root.left, index, sb);
else
index = decode(root.right, index, sb);
return index;
}
// Builds Huffman Tree and huffmanCode and decode given input text
public static void buildHuffmanTree(String text)
{
// count frequency of appearance of each character
// and store it in a map
Map<Character, Integer> freq = new HashMap<>();
for (int i = 0 ; i < text.length(); i++) {
if (!freq.containsKey(text.charAt(i))) {
freq.put(text.charAt(i), 0);
}
freq.put(text.charAt(i), freq.get(text.charAt(i)) + 1);
}
// Create a priority queue to store live nodes of Huffman tree
// Notice that highest priority item has lowest frequency
PriorityQueue<Node> pq = new PriorityQueue<>(
(l, r) -> l.freq - r.freq);
// Create a leaf node for each character and add it
// to the priority queue.
for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
pq.add(new Node(entry.getKey(), entry.getValue()));
}
// do till there is more than one node in the queue
while (pq.size() != 1)
{
// Remove the two nodes of highest priority
// (lowest frequency) from the queue
Node left = pq.poll();
Node right = pq.poll();
// Create a new internal node with these two nodes as children
// and with frequency equal to the sum of the two nodes
// frequencies. Add the new node to the priority queue.
int sum = left.freq + right.freq;
pq.add(new Node('', sum, left, right));
}
// root stores pointer to root of Huffman Tree
Node root = pq.peek();
// traverse the Huffman tree and store the Huffman codes in a map
Map<Character, String> huffmanCode = new HashMap<>();
encode(root, "", huffmanCode);
// print the Huffman codes
System.out.println("Huffman Codes are :n");
for (Map.Entry<Character, String> entry : huffmanCode.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
System.out.println("nOriginal string was :n" + text);
// print encoded string
StringBuilder sb = new StringBuilder();
for (int i = 0 ; i < text.length(); i++) {
sb.append(huffmanCode.get(text.charAt(i)));
}
System.out.println("nEncoded string is :n" + sb);
// traverse the Huffman Tree again and this time
// decode the encoded string
int index = -1;
System.out.println("nDecoded string is: n");
while (index < sb.length() - 2) {
index = decode(root, index, sb);
}
}
public static void main(String[] args)
{
String text = "Huffman coding is a data compression algorithm.";
buildHuffmanTree(text);
}
}
рдЯреАрдк: рдЗрдирдкреБрдЯ рд╕реНрдЯреНрд░рд┐рдВрдЧрджреНрд╡рд╛рд░реЗ рд╡рд╛рдкрд░рд▓реЗрд▓реА рдореЗрдорд░реА 47 * 8 = 376 рдмрд┐рдЯреНрд╕ рдЖрд╣реЗ рдЖрдгрд┐ рдПрдиреНрдХреЛрдб рдХреЗрд▓реЗрд▓реА рд╕реНрдЯреНрд░рд┐рдВрдЧ рдлрдХреНрдд 194 рдмрд┐рдЯреНрд╕ рдЖрд╣реЗ. рдбреЗрдЯрд╛ рд╕реБрдорд╛рд░реЗ 48% рд╕рдВрдХреБрдЪрд┐рдд рдХреЗрд▓рд╛ рдЖрд╣реЗ. рд╡рд░реАрд▓ C++ рдкреНрд░реЛрдЧреНрд░рд╛рдордордзреНрдпреЗ, рдкреНрд░реЛрдЧреНрд░рд╛рдо рд╡рд╛рдЪрдиреАрдп рдмрдирд╡рдгреНрдпрд╛рд╕рд╛рдареА рдЖрдореНрд╣реА рдПрдиреНрдХреЛрдб рдХреЗрд▓реЗрд▓реА рд╕реНрдЯреНрд░рд┐рдВрдЧ рд╕рд╛рдард╡рдгреНрдпрд╛рд╕рд╛рдареА рд╕реНрдЯреНрд░рд┐рдВрдЧ рдХреНрд▓рд╛рд╕ рд╡рд╛рдкрд░рддреЛ.
рдХрд╛рд░рдг рдХрд╛рд░реНрдпрдХреНрд╖рдо рдкреНрд░рд╛рдзрд╛рдиреНрдп рд░рд╛рдВрдЧреЗрддреАрд▓ рдбреЗрдЯрд╛ рд╕реНрдЯреНрд░рдХреНрдЪрд░реНрд╕рдирд╛ рдкреНрд░рддрд┐ рдЗрдиреНрд╕рд░реНрдЯреЗрд╢рди рдЖрд╡рд╢реНрдпрдХ рдЖрд╣реЗ рдУ(рд▓реЙрдЧ(рдПрди)) рд╡реЗрд│, рдкрдг рд╕рд╣ рдкреВрд░реНрдг рдмрд╛рдпрдирд░реА рдЯреНрд░реА рдордзреНрдпреЗ N рдкрд╛рдиреЗ рдЙрдкрд╕реНрдерд┐рдд 2N-1 рдиреЛрдбреНрд╕, рдЖрдгрд┐ рд╣рдлрдорди рдЯреНрд░реА рд╕рдВрдкреВрд░реНрдг рдмрд╛рдпрдирд░реА рдЯреНрд░реА рдЖрд╣реЗ, рдирдВрддрд░ рдЕрд▓реНрдЧреЛрд░рд┐рджрдо рдЪрд╛рд▓рддреЗ O(Nlog(N)) рд╡реЗрд│, рдХреБрдареЗ N - рдкрд╛рддреНрд░реЗ.
рд╕реНрддреНрд░реЛрдд:
рд╕реНрддреНрд░реЛрдд: www.habr.com