Run Length EncodingDescription
) q+ }" Z! u3 x$ r, R2 a
2 H, N: A3 d! T* ^ `Your task is to write a program that performs a ** form of run-length encoding, as described by the rules below.
. E1 X5 V" k2 p! x6 n' n/ l! e
. P& m0 _! |0 D5 O, P+ d6 Q% DAny sequence of between 2 to 9 identical characters is encoded by two characters. The first character is the length of the sequence, represented by one of the characters 2 through 9. The second character is the value of the repeated character. A sequence of more than 9 identical characters is dealt with by first encoding 9 characters, then the remaining ones. 5 H, w: j7 A) v" g3 y* ^- D
* j( `- H# z6 R
Any sequence of characters that does not contain consecutive repetitions of any characters is represented by a 1 character followed by the sequence of characters, terminated with another 1. If a 1 appears as part of the
1 C: ]- v6 ?9 A; Ysequence, it is escaped with a 1, thus two 1 characters are output. 3 K6 J [; c* Y/ H* v6 X p' o
4 K6 x2 X2 K, k; p+ T: F. ]! g" n( a9 kInput
. _7 t8 [8 i. z, H
2 ?+ r% c5 C- q! ]" vThe input consists of letters (both upper- and lower-case), digits, spaces, and punctuation. Every line is terminated with a newline character and no other characters appear in the input. 4 N' B: J9 q! Y3 V
- [ T8 g; B" M( s' [9 N$ S, dOutput 6 Q% A4 }# o! V- B
" r$ ^: Y6 b9 m1 _2 y: p
Each line in the input is encoded separately as described above. The newline at the end of each line is not encoded, but is passed directly to the output. & w. F, | t: x j
" X9 T& c0 P) r" G
输入样例 5 c9 U; m8 \0 {# k) Q# d' i) G1 _+ b
AAAAAABCCCC: A2 [) D; _. n( W+ z
123444 p& [% a4 R; v; @3 o
5 i9 e% e9 t' K; h. J8 _& B( H
& L J5 j+ t% N输出样例
) T" E" G+ H- P, v" ?' H- e6A1B14C/ u9 a; N0 g' _# L
111231247 }/ k, P) `; H0 R- `
5 l( \$ }# ]: G
1 P5 o2 E `$ [: x9 M z! V" k% O9 FSource' p' p3 u: N W5 i: v) k! P: ~
/ a5 j0 z# _+ e. pUlm Local 20045 z: p% S$ B: W; `: ]/ N- G
1 s* w( P; |0 G; a }
example1:
; }: f- K* X& F; ? @5 L2 w#include<stdio.h>& ?+ }- a. o% \& I
#include<string.h>7 O2 L: f# S* j# w5 L
void main()& h- m9 n3 U- R2 }! F1 G/ X
{ int i,j,k,n;: i. X4 K# _- o+ t1 N$ ^" L- J
char a[50];4 w0 @8 ^- Z, |8 F$ X4 W
gets(a);7 C# Z7 F, `; N" u D6 e
n=strlen(a);
: }! M: S0 U7 w6 k, d- M
9 o# G7 f% G# P0 l# B% i- N for(i=0;i<n-1; )
/ {7 ~# p2 T8 I# D if(a==a[i+1]); j, X+ h5 O, q1 }6 e: F. e8 r/ W
{ for(j=i+1;a[j]==a[j+1];j++);* t+ k: w" x/ [
printf("%d%c",j-i+1,a);8 K! u( Y; v8 y( c) _) V& ^: Y
i=j+1;
: u" N# w2 ]$ n2 r }% N% E+ m, z$ @; @7 \8 K! B
else6 z; D; W! b1 K. p, }
{ if(a==1)
( ~. P' n4 I3 F: D { printf("11");
: ~ E2 f; J7 ?0 H1 Z# B( H i++;6 s5 P# x' T7 P2 f! c
}
( `* A) |3 l' l1 a2 [ else1 N& p1 D( C. A6 b) `9 n5 v
{ for(j=i+1;a[j]!=a[j+1];j++);
( D- H8 O" h. T% d; T printf("1");
+ ]- [" J4 r! G r6 M/ N if(j==n+1)8 N4 l+ a- g$ d" q$ _3 c0 u: n
j--;
0 Y) T. g2 M# J G6 d for(k=i;k<j;k++)% M% B% h* p( S# A- n; ^: U. Y1 ?) j7 r
printf("%c",a[k]);
3 S5 }% x6 \! d& Q7 H' h1 H& z printf("1");
5 A% E; F+ |" N7 m6 f5 g! U i=j;4 @( o( l5 e# e
}
: a, ]2 O% N" G9 R }5 D \6 }# N# {9 t' u
if(n==1). k$ m, \* [: o7 V$ R
if(a[0]=='1')
+ Y: i6 O: H2 w+ h+ A printf("11");
7 y3 I2 a( ~9 T9 x( i* s a& ^ else9 n/ V. o$ y2 W: g) `0 y
printf("1%c1",a[0]);
4 u7 |* {+ O! v2 t: o% } printf("\n");( d! b/ M, {! ]& l' @/ k( U
}6 y6 B, F9 z6 L7 M! f
评论人: Colby 发布时间: 2010-3-2 12:04:06 #include<stdio.h>1 ~6 N5 j, D/ X& G) U7 f2 [3 @# ]+ i
#include<string.h>0 x' t' Q% R1 r7 m: v/ S5 m# j
void main()* F, V, ~! q7 v! \: f6 m
{ int i,j,k,n;2 x7 v/ I9 N6 U; l- @
char a[50];
# u- ~( c J+ w8 y9 i. k: [4 h gets(a);' P% P' Q0 | |5 D/ C* o
n=strlen(a);2 r% w; }1 f3 i7 c
) s( \: i4 [- [6 ?/ {2 z for(i=0;i<n-1; )
& e, g2 Z7 L2 s/ j8 x% d/ s if(a==a[i+1])& w4 @8 F. M9 h) ]; \
{ for(j=i+1;a[j]==a[j+1];j++);
" z- {# a/ C. u5 l: y# \ printf("%d%c",j-i+1,a);
/ w7 {8 \) s" A9 X; Z. G. @: w, ~4 D i=j+1;! s# ^7 D4 Y- {$ _! W, a- C
}% U9 F( u% q. q6 J2 [
else
, ?! F V3 \$ C$ X2 n, h3 k { if(a==1)
- K" z) a o, ? { printf("11");1 K% |4 m/ j4 B k7 a% n
i++;
3 t* B1 Q& v3 n8 e }
7 @+ d0 N% ^: N0 {. ^# a else
! [: X& o7 J, }6 A! _ { for(j=i+1;a[j]!=a[j+1];j++);
; ]$ t& B( S7 x5 Y; g& B. g+ r printf("1");
1 P- V5 ?1 ~5 D0 f& X5 ` if(j==n+1)* H+ \ f* B5 ?
j--;
. Q0 x) r$ a) b) ^" V for(k=i;k<j;k++). e" I' Y. y" F9 B; W
printf("%c",a[k]);3 l6 M- c2 o9 A( s0 J+ ~. [4 C
printf("1");/ J+ H0 K) Y7 Z5 Z3 v8 [
i=j;* w! \. H* [% R' O+ F
}; @ [' Y" C4 n# S. X3 `- p
}( I: H z. z" G9 G* f! [
if(n==1)$ b: a# W! b4 W( D5 ]) x8 m# B
if(a[0]=='1')* |, q( i; b+ c' l
printf("11");
( \- Z- _1 H$ e/ n: ~: G else
( I; A/ K3 P" N; l7 |' x printf("1%c1",a[0]);
M, W$ L$ w% r4 ? printf("\n");
5 k2 {% I8 E3 q9 ` } example2:#include<stdio.h>
r0 ]( A9 p( s! h' w#include<string.h>* f7 c; i5 K; Q5 ?( {" ~
void main()1 r5 o6 i" k* s" L9 l5 Y$ M
{ int i,j,k,n;0 `5 [ f0 N" g8 n0 M
char a[50];
7 N. e9 s+ a' I6 A3 I0 q8 B- Q gets(a);3 J1 w# _% d: W- D* c
n=strlen(a);
" | u6 k9 q' _1 x4 Y5 r: \% e
! b b2 U% q7 P- K( T. a3 i for(i=0;i<n-1; )$ ?" q2 v# I* R8 z0 c$ N9 F3 d* ^
if(a==a[i+1])2 T1 r. A& `! V% L/ ^
{ for(j=i+1;a[j]==a[j+1];j++);; ?7 {, @2 \) @4 Y7 I6 {( t" B; Z
printf("%d%c",j-i+1,a);
0 {0 V( y# P2 f- M i=j+1;
- z* `( Z/ Q/ N+ L5 S8 d+ N G: v6 g }
P: Q3 y7 Y f. Y) ?6 T+ L else
! ?! W6 Y" j+ U/ @. R/ K& d { if(a==1)
2 v" H* h* D+ T$ ]) o% [2 W( g6 D% b { printf("11");9 r4 D5 l5 H9 V5 ?7 `- i2 k
i++;
. j* X1 C3 j# X# \, r$ u+ k }0 r% a: @* t7 \3 n0 u+ F
else
+ Z) m M- x0 l5 Z$ c9 A' k7 M4 w { for(j=i+1;a[j]!=a[j+1];j++);
) l1 D" H/ Z- t! B$ H; W printf("1");! P# |; w9 L5 w) I
if(j==n+1)" B! H+ J$ N `5 Q% b1 O
j--;5 y3 x g/ B1 x
for(k=i;k<j;k++)9 H9 x! q& ]% s% \4 m
printf("%c",a[k]);7 |9 s5 p4 Z y) R( N$ H5 ]
printf("1");+ M2 T: ^6 P5 j+ c( q2 R2 T! }
i=j;" y! G/ ?, w+ E; W
}
. a6 r% a) L, f4 P }. t+ u( V/ ?6 O
if(n==1)0 ]1 K2 e. L7 w# N& W1 [
if(a[0]=='1')/ v$ e+ c( e4 r1 T
printf("11");/ H* f# {+ I% W# g; S6 E. Y% P3 Z
else
) e: S- ]' B' H) b7 \ printf("1%c1",a[0]);9 U* E( i3 ~$ z {
printf("\n");
7 E: Y+ @2 m0 t1 t# U }
$ l" k- B1 s8 j9 u$ \: i example3:#include<stdio.h>) Q: N: Z$ g3 z. F: O
#include<string.h>
. C v; r+ C# O/ Hvoid main()
3 ^8 V% m+ Z! C: N N$ f4 p{ int i,j,k,n;# y; G4 Y$ g0 u1 f H! o0 |! t
char a[50];
: M0 O- X% _3 c& U' @ gets(a);
' n. V3 C0 f2 g! g5 R' t: V) o n=strlen(a);, g6 r j/ ~, w
% |3 v6 E7 y3 v) V for(i=0;i<n-1; )4 }5 z" z8 E/ P" L
if(a==a[i+1])0 i: z* F. X! H3 V- R X
{ for(j=i+1;a[j]==a[j+1];j++);; B5 e! c ? I; }% q; ]" H9 `
printf("%d%c",j-i+1,a);0 s; h( `+ ?. u1 {1 r
i=j+1;
+ g* v7 b6 X+ p! Y! w }" X$ N) p# }9 P0 W; O/ m6 \+ h3 g
else
. Q0 y5 ~1 E+ a# C: ?" v { if(a==1)" ~8 s5 r' r& v# H' K
{ printf("11");
" k I7 g, }* s# X3 R! o, a* R; f# o i++;
6 ]7 H4 Z$ y% ~ }, I" O+ p7 k8 S
else* j8 h7 @' ]3 j, @* v; C2 @6 ^! t- u
{ for(j=i+1;a[j]!=a[j+1];j++);
# x' C5 \9 c- t printf("1");: [5 P# Q4 q" W5 a' b: u
if(j==n+1)7 x/ p3 k' s5 m2 _
j--;
" j$ c k# u. T2 b% \ for(k=i;k<j;k++)
5 f) P7 T* U) G+ B& [2 t printf("%c",a[k]);% h4 B E$ h2 n( g
printf("1");
* ^8 b! P l& U$ y h3 s i=j;% w% V! }7 c0 ^
}
5 E2 B7 G* s( O1 Z" r; j }
2 D: `2 W& y. V if(n==1)
+ A# y% z/ r0 T# _ if(a[0]=='1') t# s5 e5 B' P) O
printf("11");
' k. {/ M# d% T$ F else
0 V0 i% l2 a% j0 i% I& @, z2 e printf("1%c1",a[0]);
+ m/ F. D2 ?! N6 G printf("\n");2 ^& I: P0 L* s+ a; j
}, c1 R8 [0 Q$ q4 A# w W
来源:编程爱好者acm题库 |