Run Length EncodingDescription " o8 ^7 u& Z$ @& c/ a
! m# H: x% d2 ]" R% M- T* z# d3 A+ L
Your task is to write a program that performs a ** form of run-length encoding, as described by the rules below.
z# G( _0 a9 G! ]" |4 ^* X" z7 ~& S+ h4 L3 ~- |3 S
Any 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.
& b0 W; d3 q' y8 o/ r1 E- a8 V
3 @/ ]4 r3 Z1 P/ X$ f) VAny 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
$ s0 {5 w8 f4 ~) }4 Y/ B& fsequence, it is escaped with a 1, thus two 1 characters are output. ( {8 {$ C" _" Z. ~* U2 Z
4 K' {% h) [) d, {2 E
Input # t1 D, x9 ?9 W$ J) n
) V q0 a; @4 W" \, D( |/ 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. ' W* j/ e; R8 v- K
* U3 \ n7 R2 X6 Z C7 g4 }
Output
) ^9 o6 E7 k# g- y
! x [$ t$ \7 Y4 ZEach 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.
4 o9 B$ J- l" J$ n
; _* P1 ]5 F- b3 ?1 }" ^& I输入样例 , r1 a7 Z# g* M2 _, l/ H3 w
AAAAAABCCCC
- l1 D7 U# a0 B5 e6 D- F0 c6 q+ e12344: o; x: v. z6 R. k. Y
, i# |3 G4 t, J6 Y i2 C
- \6 ~5 K/ _' j; v3 I. Q" X输出样例 $ N0 Y+ `9 {4 V" P" V
6A1B14C
& n+ A3 P* k% H9 d. {7 R0 \1 P, ]- ~11123124
3 }8 J) q2 f* J) v- d$ m6 b
& u6 A8 _7 j1 R2 O3 G1 M$ o4 [# H3 P2 o! c6 h
Source# j0 x& U: d2 B# P" P
0 T3 h; h! O7 z. B e+ l$ r
Ulm Local 2004$ k) J* p7 I0 [ K7 j1 u! B
/ v$ t8 B/ q4 _& c0 uexample1:. g/ {1 T; u5 `3 F3 G9 c
#include<stdio.h>
8 `/ p& a6 b: g* v#include<string.h>4 M# `8 z! \& _, h- m
void main()! H5 `! K6 l/ O# p2 H J, A: J
{ int i,j,k,n;' ^4 G, f; F1 ?3 _; k/ F
char a[50];8 h" L$ X0 m* {
gets(a);' y: h0 j% ~9 Z; y
n=strlen(a);& F- M, h& S( O9 x
5 {7 ]+ T/ ?7 j V) }7 `& D" s for(i=0;i<n-1; )
* b# b6 N. y! i$ y# P3 ] if(a==a[i+1])
% O* a" J5 r3 F0 L: H D { for(j=i+1;a[j]==a[j+1];j++);
& ~1 ~( r2 N" w3 E: d7 T printf("%d%c",j-i+1,a);" e$ J) E3 H X* Z- W! \
i=j+1;
" I7 D9 v3 s) D! a( q0 b6 h }
0 n$ }: a( B% v0 S else1 z+ Q& G+ \7 B9 n
{ if(a==1)
+ a D5 m. m7 d$ z# b { printf("11");! s& _. G Z3 o8 q- i9 j
i++;4 \+ ` R; ?# R1 i0 }" d2 M
}2 _# Z* I% x; ]
else
4 ]+ W @1 ?6 F1 {# i- K { for(j=i+1;a[j]!=a[j+1];j++);
7 Z/ U: V9 Q2 a! U5 W7 L printf("1");5 }. d3 d3 B3 K2 e' g0 Q0 I
if(j==n+1)
1 x( I7 F/ J* z Q5 v; l. u- g j--;: }. T2 i( ?8 r; ` m; V' G& o1 ?/ @, ]
for(k=i;k<j;k++)
6 d1 \& t: ]' a/ D" g6 _; C1 A printf("%c",a[k]);; N/ T) G# f! b3 X, G; o$ E3 d
printf("1");7 ~" Q5 ]; |8 _3 [
i=j;+ V" B: K1 ] H9 [/ P: r
}8 h; I; c9 R- E) ]+ l
}& E6 V" m+ [, H* l; h6 D
if(n==1)" d; o2 a) h- g( x" y* P
if(a[0]=='1')6 D, A: A) b; m7 J y7 F
printf("11");, `( v j; n' f! Z' U
else& e: r$ I. M" m; S
printf("1%c1",a[0]);6 [8 [' e: I+ K* @8 c+ A/ I
printf("\n");- W1 E$ |7 \+ n7 J4 E
}2 U* D) r2 i. Q, h! v; K
评论人: Colby 发布时间: 2010-3-2 12:04:06 #include<stdio.h>
S9 _( S& P: \- E4 c/ E+ L# p#include<string.h>, N, I# J: N# l& a0 w
void main()1 f7 a2 z5 Q* V' t6 w8 h* ?
{ int i,j,k,n; H# O# E* r) C: T O
char a[50];9 W5 d7 a2 J4 p) P' T+ P
gets(a);
; X( D) q5 W$ [( D- f n=strlen(a);' l! C U0 L2 h, r7 D7 X1 t1 p
. x8 w1 k/ p, ` for(i=0;i<n-1; )
' J- `0 t, W! F* I2 |# C z( j if(a==a[i+1])
. E+ o1 O1 Z1 z( { { for(j=i+1;a[j]==a[j+1];j++);6 `1 J+ a8 O& v' E3 W4 f
printf("%d%c",j-i+1,a);
6 Z9 D. ^8 I h: F i=j+1;
' Y$ s/ d' W) A }
3 o$ m7 k; v% [& K4 P$ L else
: L4 W2 i" u; b: T0 a; D { if(a==1)
) Y3 D" S z# }5 h& x3 w- G1 o+ r { printf("11");: ^( _1 _. V5 B, e- g; E, A) V4 {
i++;' R0 s5 y2 y: B% r' _: w$ @6 i- h
}' L; t5 ~6 l* P8 n6 e9 s: h
else& u$ ~' ?+ ?& e' m/ j2 z e, a K4 X& ~
{ for(j=i+1;a[j]!=a[j+1];j++);
3 ^$ g/ d' \% E2 c, x% g3 z( J printf("1");
+ z5 w- ~4 s8 h ^, ^. | if(j==n+1)
; k: J( S6 D, A o j--;$ o$ @, A' t7 ~5 p
for(k=i;k<j;k++)6 a# k9 M4 O, ^- B1 D4 i- G1 a
printf("%c",a[k]);
# j. U4 N" K1 c0 }9 l3 y: d printf("1");
6 ~9 m1 M9 B$ I% I& D6 G7 A i=j;4 J3 ~ _3 a3 T+ R) A# ?, l
}
6 ^. K; E2 d/ p4 B }
- {- D+ W9 c5 r$ {; m/ _ if(n==1)& f3 B- @! W4 L
if(a[0]=='1'), N# m1 ~/ h S9 @$ X( e4 C) H
printf("11");
5 i- ~+ e; i5 J else
l& g) P: x9 T* e% E* s( h6 e9 h. ^ printf("1%c1",a[0]);$ |3 {& O. \/ W) t
printf("\n");
3 |% E3 h( ] V0 }, E( y } example2:#include<stdio.h>
/ e( m x+ c) m+ u7 g4 m5 v#include<string.h>$ H5 a1 b8 h+ U1 G6 o: H1 F4 g% Z
void main()
. W3 z7 ]6 H! d9 S{ int i,j,k,n;
! z: ]4 r$ ]% b char a[50];
' U; _! L$ ^( _9 X% d U gets(a);
( ^" Q3 v4 k6 t: K2 _! O n=strlen(a);' G: ~; Q; {2 x H1 ~, P) m' d
) S/ L- E! E# M
for(i=0;i<n-1; )
. D$ ~5 h( H2 N# T8 r if(a==a[i+1])
q- X, U) l" e5 V8 ~ { for(j=i+1;a[j]==a[j+1];j++);
. y; _5 k. c2 I printf("%d%c",j-i+1,a);7 o, w1 ?* W5 W+ \
i=j+1;
5 z. `- T# ]9 M& L! [/ a* P }2 ^6 h1 h" q/ g7 H7 K7 _
else
( u/ I6 V. y$ W% [" H* O: g" C { if(a==1)" V( L: z) }& [& f, a2 w6 d, @
{ printf("11");) o: u( d* ?- C4 J u* k
i++;
8 M+ @( t. b7 W U/ a3 l }
5 t* X% V3 A( A6 h" H; K! ? else) `% Q. H. ]9 d" B
{ for(j=i+1;a[j]!=a[j+1];j++);" h% X- G6 U0 _1 w- a% G' y
printf("1");: E) s2 P* p5 Z5 h, q
if(j==n+1)
% Q# [% ]$ }& U- x- j9 D; b j--;6 j: M$ N5 c [, p+ b& p
for(k=i;k<j;k++)
& }! f$ n/ `! N E+ U4 X$ C printf("%c",a[k]);
, q; Q0 K. I* n( F- ^( h/ B4 o printf("1");3 E' j, u5 ]; ~! y5 ~, a
i=j;- R9 z F( X" M% Q
}
, |1 T. k3 K$ e- g- v1 ? }
+ ~4 f. u9 I4 I2 L( s* E0 D if(n==1)' L0 B/ S3 I! ]
if(a[0]=='1')
+ r- n" \/ S0 ?2 r printf("11");
( c8 i& j* b V- M$ C$ b else
; r. Q" V6 H) ^: s6 n" o# r printf("1%c1",a[0]);- H7 Z7 z7 E2 V" p
printf("\n");
$ d( r& U ^& }7 w! K9 r }
9 G- C0 U( E( ^7 z2 `: e example3:#include<stdio.h>
$ {6 j+ L! o" w: {' h#include<string.h>
R0 l1 }" v1 h+ P: Qvoid main()+ y8 Z$ ` F% a
{ int i,j,k,n;
% K. A9 m( f3 M char a[50];0 @* a+ q1 @0 d6 s) I
gets(a);% L+ ?8 p) \1 G8 n! ^4 K& p+ i" s# g$ o
n=strlen(a);+ E& z3 B2 Z2 S. S; U- |, P7 n/ Z
9 V) z8 [9 T- w. u# f+ ~ for(i=0;i<n-1; )( n6 J# y+ G5 ?" A: e5 [# M" z
if(a==a[i+1])
( N J+ V# b4 U6 Q, t8 M( F5 D0 z { for(j=i+1;a[j]==a[j+1];j++);
+ R8 B; E5 w8 m9 K printf("%d%c",j-i+1,a);- M! E$ f# P1 B% M5 _ y! D
i=j+1;" u6 F' c6 ?! T4 G& ?
}0 [& r. _5 h/ F+ Q7 |
else0 {2 [ b- z" w
{ if(a==1)
; P6 {( Q" b f: o0 I { printf("11");
0 i- x: W4 \. D& { i++;& c9 o' b- P2 _! {
}
S2 Z: q6 P8 ^ m0 T! h else) _. U8 k! M& W5 u0 F
{ for(j=i+1;a[j]!=a[j+1];j++);' ?( G0 v4 ]9 f8 u" I7 n0 r8 ?
printf("1");
+ O- `$ n& g" T( I( @. r if(j==n+1)5 |/ } @! \/ ^; p# q
j--;1 {7 X1 P Y- z
for(k=i;k<j;k++)" A0 V6 D h* g
printf("%c",a[k]);$ G8 i2 J+ i! H* ^3 x3 Z' r! U9 C; f& y
printf("1");
. u8 M& c% F; Q; E& D- \. M; } i=j;$ z0 N$ G3 I5 z: x% A" N. ~
}
4 i. z# u. k# S& h }
" }, ~$ a* n$ ~ if(n==1)4 b/ n; p, Z1 L/ e3 v9 }$ n ~
if(a[0]=='1') `2 j$ h, v) m) \
printf("11");+ t+ T+ P! Y, V0 y6 d; V7 N" \! ?: }
else% R6 Z5 ^: n/ r' Y4 |2 k( C
printf("1%c1",a[0]);. s. f( \* w; L3 C' d9 ]
printf("\n");
2 B5 `$ v0 T4 t, m% ^% U }0 |1 T( [, x/ E& [5 |9 ^
来源:编程爱好者acm题库 |