Trang 3 trên tổng số 3 Đầu tiênĐầu tiên 123
Từ 21 tới 24 trên tổng số 24 kết quả

Đề tài: Mã hóa văn bản gửi ra ngoài hành tinh

  1. #21
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    599

    Mặc định Mã hóa văn bản gửi ra ngoài hành tinh

    Sau đây là vài cách giải.

    Mã nguồn có 2 phiên bản, v1 và v2. v1 tuân thủ đề bài một cách tuyệt đối: chỉ viết thêm hàm encodedecode ở cuối file, không sửa gì khác. v2 thêm hàm test2 và viết thêm vào hàm main để chạy test này.

    Mỗi cách giải ứng với một VERSION trong mã nguồn. Mỗi cách giải đều đáp ứng yêu cầu (cơ bản) của đề bài, nhưng có những cách còn đáp ứng một yêu cầu (nâng cao) không có trong đề bài: bản mã cũng phải là một C-string như nguyên bản. Đó là VERSION 2 trong mã nguồn v1, và các VERSION 2, 3 trong mã nguồn v2.

    Sẽ nói thêm sau.

    flipcode_v1.c
    C Code:
    1. /* .ZNXZNZXNXZXNZNXZNZXNZNXZXNXZNZXNXZXNZNXZXNXZNZXNZNXZNZXNXZXNZNXZ. */
    2. /*
    3.  * "You named Stalin but didn't mention Churchil or Rosevelt while you
    4.  * were talking about the UK and the US without saying a word about
    5.  * the USR or Rusia. You named Voltaire, Montesquieu, Diderot, but
    6.  * didn't mention Jean Jaques Rouseu. You like Mozart and Chopin; but
    7.  * how about Bethoven? How could you talk about Albert Einstein without
    8.  * talking about Isac Newton? Why did you name Leonhard Euler without
    9.  * mentioning Carl Friedrich Gaus? You know of Alan Turing and Kurt
    10.  * Goedel; do you know who are John von Neuman and Haskel Broks Cury?"
    11.  * [TX S-T computed: Earth 1967-10-28 23:59:02.718281828459045235 GMT]
    12.  *
    13.  * "I know persons and countries you've named, and more. John Lenon and
    14.  * Luciano Pavaroti. Sean Conery and Dustin Hofman. Whitfield Difie
    15.  * and Martin Helman. Denis Ritchie and Richard Stalman. I know even
    16.  * Bil Gates and Marisa Mayer. I know what is Aple, Gogle, Facebok,
    17.  * Yaho, and I'm aware of the C+ programing language. I just don't want
    18.  * to lok like a ten-ager by mispeling their names."
    19.  *
    20.  * "At terminal velocity, time becomes relativistic. My transceiver
    21.  * isn't clock-based. A signal can be synchronised only with itself.
    22.  * Every symbol acts like a 'clock cycle' of its own, so it must be
    23.  * signified by a change in the signal. In quantum time, a symbol which
    24.  * duplicates the one right before it can't be recognised. I can only
    25.  * receive and transmit a symbol which is distinct from the imediately
    26.  * preceding one. For proper comunication, encode mesages in a format
    27.  * with solely such 'flip' and no such 'twin' symbols. Complete this C
    28.  * programe with your coding algorithm, test it with real texts in your
    29.  * languages and send it back before actual use."
    30.  * [RX S-T expected: Earth 2017-10-28 23:59:03.141592653589793238 UTC]
    31.  */
    32. /* .-|+-|-+|+-+|-|+-|-+|-|+-+|+-|-+|+-+|-|+-+|+-|-+|-|+-|-+|+-+|-|+-. */
    33. long encode(long n, char *x);
    34. /*
    35.  * Encode C-string x, up to n+1 chars. Return #encoded chars - 1
    36.  */
    37. long decode(long n, char *x);
    38. /*
    39.  * Decode x, up to n+1 chars, to C-string. Return #decoded chars - 1
    40.  */
    41. /* .-|+-|-+|+-+|-|+-|-+|-|+-+|+-|-+|+-+|-|+-+|+-|-+|-|+-|-+|+-+|-|+-. */
    42. #include <stdio.h>
    43. #include <stdlib.h>
    44. #include <string.h>
    45. #include <math.h>
    46. /* .-|+-|-+|+-+|-|+-|-+|-|+-+|+-|-+|+-+|-|+-+|+-|-+|-|+-|-+|+-+|-|+-. */
    47. void take(int b, int kod, const char *msg, int id)
    48. {
    49.  if(!b){ printf("%d:%s\n",id,msg); exit(kod); }
    50. }
    51. /* .-|+-|-+|+-+|-|+-|-+|-|+-+|+-|-+|+-+|-|+-+|+-|-+|-|+-|-+|+-+|-|+-. */
    52. void fail(int b, int kod, const char *msg, int id)
    53. {
    54.  if(b) { printf("%d:%s\n",id,msg); exit(kod); }
    55. }
    56. /* .-|+-|-+|+-+|-|+-|-+|-|+-+|+-|-+|+-+|-|+-+|+-|-+|-|+-|-+|+-+|-|+-. */
    57. #define FINPUT 1 /* Input failure */
    58. #define FSAMPL 2 /* Non-suitable text sample */
    59. #define FENCOD 3 /* Encode bug */
    60. #define FDECOD 4 /* Decode bug */
    61. #define FSECUR 5 /* Security bug */
    62. #define FLOGIC 6 /* Other logical bug */
    63. /* .-|+-|-+|+-+|-|+-|-+|-|+-+|+-|-+|+-+|-|+-+|+-|-+|-|+-|-+|+-+|-|+-. */
    64. void test(int g, char *a, const char *b, long M, long L, long m)
    65. /*
    66.  * encode-then-decode test, up to m+1 chars, on a C-string of length L
    67.  * already contained in memory section a of size M+1, whose initial
    68.  * content is identical to section b and remains identical upon return
    69.  * (if any). Report failure (and exit) using g as test case ID.
    70.  */
    71. {
    72.  fail(memcmp(a,b,M+1),FLOGIC, "Logical bug: precondition #1.",g);
    73.  take(L < M, FLOGIC,"Logical bug: precondition #2.",g);
    74.  fail(L-strlen(a),FLOGIC,"Logical bug: precondition #3.",g);
    75.  take(m <=M, FLOGIC,"Logical bug: precondition #4.",g);
    76.  fail(m <-1, FLOGIC,"Logical bug: precondition #5.",g);
    77.  long n = L < m ? L : m;
    78.  long N = encode(m,a);
    79.  fail(N > n, FSECUR, "Encode bug: probably mem. violation.",g);
    80.  fail(N < n, FENCOD, "Bad encode: length mismatch.",g);
    81.  fail(memcmp(a+n+1,b+n+1,M-n), FSECUR, "Encode bug: mem. violation.",g);
    82.  for(long i=1;i<N;i+=1) take(a[i]-a[i-1],FENCOD, "Bad encode: twin.",g);
    83.  long K = decode(m,a);
    84.  fail(K > n, FSECUR, "Decode bug: probably mem. violation.",g);
    85.  fail(K < n, FDECOD, "Bad decode: length mismatch.",g);
    86.  fail(memcmp(a+n+1,b+n+1,M-n), FSECUR, "Decode bug: mem. violation.",g);
    87.  fail(memcmp(a,b,K+1), FDECOD, "Bad decode: wrong original.",g);
    88. }
    89. /* .-|+-|-+|+-+|-|+-|-+|-|+-+|+-|-+|+-+|-|+-+|+-|-+|-|+-|-+|+-+|-|+-. */
    90. #define NUL '\0'
    91. #define M ( (long)1E8 ) /* Max sample size incl. NUL terminator */
    92. /* .-|+-|-+|+-+|-|+-|-+|-|+-+|+-|-+|+-+|-|+-+|+-|-+|-|+-|-+|+-+|-|+-. */
    93. int main()
    94. {
    95.  typedef long long IN;
    96.  static char a[M+1], b[M+1];
    97.  for(long i=0;i<sizeof(a);i+=1) a[i]=b[i]=rand();
    98.  char *t = a;
    99.  *t = NUL;
    100.  for(long n=M;(n>1)*(IN)fgets(t,n,stdin);){long k=strlen(t);t+=k;n-=k;}
    101.  fail(*t != NUL, FINPUT, "Input failure #1.", 0);
    102.  long L = t - a;
    103.  take(L < M, FINPUT, "Input failure #2.", 0);
    104.  fail(L-strlen(a),FINPUT, "Input failure #3.", 0);
    105.  long nTwin = 0, nFlip = 0;
    106.  for(long i=0;i<L-1;i+=1){if(a[i]-a[i+1]) nFlip+=1; else nTwin+=1;}
    107.  take(nTwin, FSAMPL, "Bad sample: no twin symbols.", 0);
    108.  take(nFlip, FSAMPL, "Bad sample: no flip symbols.", 0);
    109.  strcpy(b,a);
    110.  test(1, a, b, M, L, M);
    111.  test(2, a, b, M, L, L+1);
    112.  test(3, a, b, M, L, L);
    113.  test(4, a, b, M, L, L-1);
    114.  test(5, a, b, M, L, L/2);
    115.  test(6, a, b, M, L, 1);
    116.  test(7, a, b, M, L, 0);
    117.  test(8, a, b, M, L,-1);
    118.  printf( "%ld symbols encoded. You got %.0f points.\n", L, log10(L) );
    119.  return 0;
    120. }
    121. /* .ZNXZNZXNXZXNZNXZNZXNZNXZXNXZNZXNXZXNZNXZXNXZNZXNZNXZNZXNXZXNZNXZ. */
    122. /*
    123.  * Put code here
    124.  *
    125.  * Define encode() and decode(), nothing else.
    126.  */
    127. #define VERSION 1
    128. /* .-|+-|-+|+-+|-|+-|-+|-|+-+|+-|-+|+-+|-|+-+|+-|-+|-|+-|-+|+-+|-|+-. */
    129. #if !(VERSION-1)
    130. long encode(long n, char *x)
    131. {
    132.  char const R = 127;
    133.  long i;
    134.  for(i=0;(i<n+1)&(x[i]!=0);i+=1) if( !(x[i]-R) ) { x[i]=0; }
    135.  if(!x[0]) return 0;
    136.  for(i=1;(i<n+1)&(x[i]!=0);i+=1) if( !(x[i]-x[i-1]) ) { x[i] = R; }
    137.  return i<n+1 ? i : n;
    138. }
    139. /* .-|+-|-+|+-+|-|+-|-+|-|+-+|+-|-+|+-+|-|+-+|+-|-+|-|+-|-+|+-+|-|+-. */
    140. long decode(long n, char *x)
    141. {
    142.  char const R = 127;
    143.  long i;
    144.  if(!x[0]) return 0;
    145.  for(i=1;(i<n+1)&(x[i]!=0);i+=1) if( !(x[i]-R) ) { x[i] = x[i-1]; }
    146.  return i<n+1 ? i : n;
    147. }
    148. /* .-|+-|-+|+-+|-|+-|-+|-|+-+|+-|-+|+-+|-|+-+|+-|-+|-|+-|-+|+-+|-|+-. */
    149. #elif !(VERSION-2)
    150. long encode(long n, char *x)
    151. {
    152.  long s = 0;
    153.  for(long i=0;i<n+1;i+=1){ x[i]+=s; if( !(x[i]-s) ) return i; s=x[i]; }
    154.  return n;
    155. }
    156. /* .-|+-|-+|+-+|-|+-|-+|-|+-+|+-|-+|+-+|-|+-+|+-|-+|-|+-|-+|+-+|-|+-. */
    157. long decode(long n, char *x)
    158. {
    159.  long s = 0;
    160.  for(long i=0;i<n+1;i+=1){ x[i]-=s; s+=x[i]; if(!x[i]) return i; }
    161.  return n;
    162. }
    163. #endif
    164. /* .ZNXZNZXNXZXNZNXZNZXNZNXZXNXZNZXNXZXNZNXZXNXZNZXNZNXZNZXNXZXNZNXZ. */

    flipcode_v2.c
    C Code:
    1. /* .ZNXZNZXNXZXNZNXZNZXNZNXZXNXZNZXNXZXNZNXZXNXZNZXNZNXZNZXNXZXNZNXZ. */
    2. /*
    3.  * "You named Stalin but didn't mention Churchil or Rosevelt while you
    4.  * were talking about the UK and the US without saying a word about
    5.  * the USR or Rusia. You named Voltaire, Montesquieu, Diderot, but
    6.  * didn't mention Jean Jaques Rouseu. You like Mozart and Chopin; but
    7.  * how about Bethoven? How could you talk about Albert Einstein without
    8.  * talking about Isac Newton? Why did you name Leonhard Euler without
    9.  * mentioning Carl Friedrich Gaus? You know of Alan Turing and Kurt
    10.  * Goedel; do you know who are John von Neuman and Haskel Broks Cury?"
    11.  * [TX S-T computed: Earth 1967-10-28 23:59:02.718281828459045235 GMT]
    12.  *
    13.  * "I know persons and countries you've named, and more. John Lenon and
    14.  * Luciano Pavaroti. Sean Conery and Dustin Hofman. Whitfield Difie
    15.  * and Martin Helman. Denis Ritchie and Richard Stalman. I know even
    16.  * Bil Gates and Marisa Mayer. I know what is Aple, Gogle, Facebok,
    17.  * Yaho, and I'm aware of the C+ programing language. I just don't want
    18.  * to lok like a ten-ager by mispeling their names."
    19.  *
    20.  * "At terminal velocity, time becomes relativistic. My transceiver
    21.  * isn't clock-based. A signal can be synchronised only with itself.
    22.  * Every symbol acts like a 'clock cycle' of its own, so it must be
    23.  * signified by a change in the signal. In quantum time, a symbol which
    24.  * duplicates the one right before it can't be recognised. I can only
    25.  * receive and transmit a symbol which is distinct from the imediately
    26.  * preceding one. For proper comunication, encode mesages in a format
    27.  * with solely such 'flip' and no such 'twin' symbols. Complete this C
    28.  * programe with your coding algorithm, test it with real texts in your
    29.  * languages and send it back before actual use."
    30.  * [RX S-T expected: Earth 2017-10-28 23:59:03.141592653589793238 UTC]
    31.  */
    32. /* .-|+-|-+|+-+|-|+-|-+|-|+-+|+-|-+|+-+|-|+-+|+-|-+|-|+-|-+|+-+|-|+-. */
    33. long encode(long n, char *x);
    34. /*
    35.  * Encode C-string x, up to n+1 chars. Return #encoded chars - 1
    36.  */
    37. long decode(long n, char *x);
    38. /*
    39.  * Decode x, up to n+1 chars, to C-string. Return #decoded chars - 1
    40.  */
    41. /* .-|+-|-+|+-+|-|+-|-+|-|+-+|+-|-+|+-+|-|+-+|+-|-+|-|+-|-+|+-+|-|+-. */
    42. #include <stdio.h>
    43. #include <stdlib.h>
    44. #include <string.h>
    45. #include <math.h>
    46. /* .-|+-|-+|+-+|-|+-|-+|-|+-+|+-|-+|+-+|-|+-+|+-|-+|-|+-|-+|+-+|-|+-. */
    47. void take(int b, int kod, const char *msg, int id)
    48. {
    49.  if(!b){ printf("%d:%s\n",id,msg); exit(kod); }
    50. }
    51. /* .-|+-|-+|+-+|-|+-|-+|-|+-+|+-|-+|+-+|-|+-+|+-|-+|-|+-|-+|+-+|-|+-. */
    52. void fail(int b, int kod, const char *msg, int id)
    53. {
    54.  if(b) { printf("%d:%s\n",id,msg); exit(kod); }
    55. }
    56. /* .-|+-|-+|+-+|-|+-|-+|-|+-+|+-|-+|+-+|-|+-+|+-|-+|-|+-|-+|+-+|-|+-. */
    57. #define FINPUT 1 /* Input failure */
    58. #define FSAMPL 2 /* Non-suitable text sample */
    59. #define FENCOD 3 /* Encode bug */
    60. #define FDECOD 4 /* Decode bug */
    61. #define FSECUR 5 /* Security bug */
    62. #define FLOGIC 6 /* Other logical bug */
    63. /* .-|+-|-+|+-+|-|+-|-+|-|+-+|+-|-+|+-+|-|+-+|+-|-+|-|+-|-+|+-+|-|+-. */
    64. void test(int g, char *a, const char *b, long M, long L, long m)
    65. /*
    66.  * encode-then-decode test, up to m+1 chars, on a C-string of length L
    67.  * already contained in memory section a of size M+1, whose initial
    68.  * content is identical to section b and remains identical upon return
    69.  * (if any). Report failure (and exit) using g as test case ID.
    70.  */
    71. {
    72.  fail(memcmp(a,b,M+1),FLOGIC, "Logical bug: precondition #1.",g);
    73.  take(L < M, FLOGIC,"Logical bug: precondition #2.",g);
    74.  fail(L-strlen(a),FLOGIC,"Logical bug: precondition #3.",g);
    75.  take(m <=M, FLOGIC,"Logical bug: precondition #4.",g);
    76.  fail(m <-1, FLOGIC,"Logical bug: precondition #5.",g);
    77.  long n = L < m ? L : m;
    78.  long N = encode(m,a);
    79.  fail(N > n, FSECUR, "Encode bug: probably mem. violation.",g);
    80.  fail(N < n, FENCOD, "Bad encode: length mismatch.",g);
    81.  fail(memcmp(a+n+1,b+n+1,M-n), FSECUR, "Encode bug: mem. violation.",g);
    82.  for(long i=1;i<N;i+=1) take(a[i]-a[i-1],FENCOD, "Bad encode: twin.",g);
    83.  long K = decode(m,a);
    84.  fail(K > n, FSECUR, "Decode bug: probably mem. violation.",g);
    85.  fail(K < n, FDECOD, "Bad decode: length mismatch.",g);
    86.  fail(memcmp(a+n+1,b+n+1,M-n), FSECUR, "Decode bug: mem. violation.",g);
    87.  fail(memcmp(a,b,K+1), FDECOD, "Bad decode: wrong original.",g);
    88. }
    89. /* .-|+-|-+|+-+|-|+-|-+|-|+-+|+-|-+|+-+|-|+-+|+-|-+|-|+-|-+|+-+|-|+-. */
    90. void test2(int g, int n)
    91. /*
    92.  * Do a random sequence of n encode-or-decode actions then the reverse
    93.  * sequence of counter-actions on a memory sector, which should revert
    94.  * to its original content when the sequences complete.
    95.  *
    96.  * Report failure using g as test case ID, and exit.
    97.  */
    98. {
    99.  long const MEM=256;
    100.  char x[MEM], y[MEM];
    101.  for(long i=0;i<MEM;i+=1) x[i]=y[i]=rand();
    102.  unsigned const a0=123456789, b0=987654321, a1=102505021, b1= -b0*a1;
    103.  fail(a0*a1-1, FLOGIC, "Bad reverse PRNG.",g);
    104.  long const m=176; /* Even point: Pr[strlen(x)<=m | x random] ~ 0.5 */
    105.  take(m<MEM, FLOGIC, "Logical bug: precondition #4.",g);
    106.  fail(m< -1, FLOGIC, "Logical bug: precondition #5.",g);
    107.  unsigned const msb=(unsigned)(-1)/2+1; /* MININT */
    108.  unsigned r = rand();
    109.  for(int k=n;k;k-=1){r = r*a0+b0; r&msb ? encode(m,x) : decode(m,x);}
    110.  for(int k=n;k;k-=1){r&msb ? decode(m,x) : encode(m,x); r = r*a1+b1;}
    111.  fail(memcmp(x,y,MEM), FSECUR, "Bad algo: non-bijective coding.",g);
    112. }
    113. /* .-|+-|-+|+-+|-|+-|-+|-|+-+|+-|-+|+-+|-|+-+|+-|-+|-|+-|-+|+-+|-|+-. */
    114. #define NUL '\0'
    115. #define M ( (long)1E8 ) /* Max sample size incl. NUL terminator */
    116. /* .-|+-|-+|+-+|-|+-|-+|-|+-+|+-|-+|+-+|-|+-+|+-|-+|-|+-|-+|+-+|-|+-. */
    117. int main()
    118. {
    119.  typedef long long IN;
    120.  static char a[M+1], b[M+1];
    121.  for(long i=0;i<sizeof(a);i+=1) a[i]=b[i]=rand();
    122.  char *t = a;
    123.  *t = NUL;
    124.  for(long n=M;(n>1)*(IN)fgets(t,n,stdin);){long k=strlen(t);t+=k;n-=k;}
    125.  fail(*t != NUL, FINPUT, "Input failure #1.", 0);
    126.  long L = t - a;
    127.  take(L < M, FINPUT, "Input failure #2.", 0);
    128.  fail(L-strlen(a),FINPUT, "Input failure #3.", 0);
    129.  long nTwin = 0, nFlip = 0;
    130.  for(long i=0;i<L-1;i+=1){if(a[i]-a[i+1]) nFlip+=1; else nTwin+=1;}
    131.  take(nTwin, FSAMPL, "Bad sample: no twin symbols.", 0);
    132.  take(nFlip, FSAMPL, "Bad sample: no flip symbols.", 0);
    133.  strcpy(b,a);
    134.  test(1, a, b, M, L, M-1);
    135.  test(2, a, b, M, L, L+1);
    136.  test(3, a, b, M, L, L);
    137.  test(4, a, b, M, L, L-1);
    138.  test(5, a, b, M, L, L/2);
    139.  test(6, a, b, M, L, 1);
    140.  test(7, a, b, M, L, 0);
    141.  test(8, a, b, M, L,-1);
    142.  for(int n=(int)1E4;n;n-=1) test2(10,101);
    143.  printf( "%ld symbols encoded. You got %.0f points.\n", L, log10(L) );
    144.  return 0;
    145. }
    146. /*23456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJKLMNOPQRSTUVWX*/
    147. /*
    148.  * Put code here
    149.  *
    150.  * Define encode() and decode(), nothing else.
    151.  */
    152. #define VERSION 3
    153. /*:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.*/
    154. #if !(VERSION-0)
    155. long encode(long n, char *x)
    156. {
    157.  if( n<0 ) return n;
    158.  if(!x[0]) return 0;
    159.  long i;
    160.  for(i=1;(i<n+1)&(x[i]!=0);i+=1) if(!(x[i]-x[i-1]) ) x[i] = NUL;
    161.  if( i<n+1 ) x[i] = x[i-1];
    162.  return i<n+1 ? i : n;
    163. }
    164. /*:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.*/
    165. long decode(long n, char *x)
    166. {
    167.  if( n<0 ) return n;
    168.  if(!x[0]) return 0;
    169.  long i;
    170.  char c = x[0];
    171.  for(i=1;(i<n+1)&(x[i]!=c);i+=1) { c=x[i]; if(!x[i]) x[i] = x[i-1]; }
    172.  if( i<n+1 ) x[i] = NUL;
    173.  return i<n+1 ? i : n;
    174. }
    175. /*:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.*/
    176. #elif !(VERSION-1)
    177. long encode(long n, char *x)
    178. {
    179.  long s = 0;
    180.  for(long i=0;i<n+1;i+=1){ x[i]+=s; if( !(x[i]-s) ) return i; s=x[i]; }
    181.  return n;
    182. }
    183. /*:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.*/
    184. long decode(long n, char *x)
    185. {
    186.  long s = 0;
    187.  for(long i=0;i<n+1;i+=1){ x[i]-=s; s+=x[i]; if(!x[i]) return i; }
    188.  return n;
    189. }
    190. /*:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.*/
    191. #elif !(VERSION-2)
    192. #define DEL '\x7F'
    193. long encode(long n, char *x)
    194. {
    195.  if( n<0 ) return n;
    196.  char const R = DEL;
    197.  if(!( (x[0]!=NUL)&(x[0]!=R) ) ) return 0;
    198.  long i;
    199.  for(i=1;(i<n+1)&(x[i]!=0)&(x[i]!=R);i+=1) if(!(x[i]-x[i-1]) ) x[i]=R;
    200.  if( (i<n+1)&!(x[i]-R) ) x[i] = x[i-1];
    201.  return i<n+1 ? i : n;
    202. }
    203. /*:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.*/
    204. long decode(long n, char *x)
    205. {
    206.  if( n<0 ) return n;
    207.  char const R = DEL;
    208.  if(!( (x[0]!=NUL)&(x[0]!=R) ) ) return 0;
    209.  long i;
    210.  char c = x[0];
    211.  for(i=1;(i<n+1)&(x[i]!=0)&(x[i]!=c);i+=1)
    212.  { c=x[i]; if(!(x[i]-R) )x[i] = x[i-1]; }
    213.  if( (i<n+1)&!(x[i]-c) ) x[i] = R;
    214.  return i<n+1 ? i : n;
    215. }
    216. /*:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.*/
    217. #elif !(VERSION-3)
    218. #define SUB '\x1A'
    219. #define ESC '\x1B'
    220. #define DEL '\x7F'
    221. typedef unsigned char ucha;
    222. /*:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.*/
    223. long encode(long n, char *scx)
    224. {
    225.  long n;
    226.  ucha const m = -1, e = DEL;
    227.  ucha s = e, * const x =(ucha*)scx;
    228.  long i;
    229.  for(i=0;(i<n+1)&(x[i]!=0);i+=1)
    230.  { ucha t=x[i]; x[i]=(t+s-e-1+m)%m+1; if(!(t-e) ) return i; s=x[i]; }
    231.  return i<n+1 ? i : n;
    232. }
    233. /*:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.*/
    234. long decode(long n, char *scx)
    235. {
    236.  ucha const m = -1, e = DEL;
    237.  ucha s = e, * const x =(ucha*)scx;
    238.  long i;
    239.  for(i=0;(i<n+1)&(x[i]!=0);i+=1)
    240.  { ucha t=x[i]; x[i]=(t-s+e-1+m)%m+1; if(!(t-s) )return i; s=t;}
    241.  return i<n+1 ? i : n;
    242. }
    243. #endif
    244. /* DIPHUSENHOPEBESTCONFVZENTHROWDYCENSAZSADATLAZTQOZSKIPJAXDAMNFRYGHT */
    Đã được chỉnh sửa lần cuối bởi Ada : 24-03-2021 lúc 09:54 PM.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  2. #22
    Ngày gia nhập
    08 2017
    Bài viết
    3,905

    Code ở trên biên dịch bằng công cụ nào?
    Với Microsoft, Borland hay MinGW đều báo lỗi. Cụ thể với Embarcadero:
    Cmd Code:
    1. F:\Work\Cpp>bcc32c flipcode_v2.c
    2. Embarcadero C++ 7.30 for Win32 Copyright (c) 2012-2017 Embarcadero Technologies, Inc.
    3. flipcode_v2.c:
    4. flipcode_v2.c:225:7: error: redefinition of 'n'
    5.  long n;
    6.       ^
    7. flipcode_v2.c:223:18: note: previous definition is here
    8. long encode(long n, char *scx)
    9.                  ^
    10. 1 error generated.

    C Code:
    1. long encode(long n, char *scx)
    2. {
    3.  long n; //redefinition of 'n'
    4.  ucha const m = -1, e = DEL;
    5.  ucha s = e, * const x =(ucha*)scx;
    6.  long i;
    7.  for(i=0;(i<n+1)&(x[i]!=0);i+=1)
    8.  { ucha t=x[i]; x[i]=(t+s-e-1+m)%m+1; if(!(t-e) ) return i; s=x[i]; }
    9.  return i<n+1 ? i : n;
    10. }

  3. #23
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    599

    Bạn bỏ dòng đó đi, sẽ compile và chạy được. Mình cũng không hiểu vì sao mình lại viết dòng đó nữa.

    Xin lỗi vì gửi bài bất cẩn.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  4. #24
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    599

    Đã có một thời không có Internet, không có SSD hay HDD, thông tin kỹ thuật số được lưu hoàn toàn trên... giấy. Mỗi văn bản là một... file, nghĩa là một tệp, giống như tệp tiền, mỗi tờ chứa 1 dòng văn bản, mỗi ký tự trên một cột, mỗi bit trên một ô. Ô trống là 0, ô đục thủng là 1. Định dạng giấy đục lỗ đó cho khả năng biên tập nhất định, tuy hạn chế. Có thể chừa ra vài cột không đục lỗ để chèn thêm (đục lỗ thêm) ký tự. Có thể xóa ký tự bằng cách đục thủng hết mọi ô trong cột.

    Vì cột với mọi ô đều trống hay cột với mọi ô đều thủng cũng vẫn là... cột, vẫn biểu thị một ký tự nhất định, nên người ta đương nhiên phải quy ước ký tự ấy là vô nghĩa. Ký tự NUL, với mọi bit đều 0, vốn ứng với cột trống mọi ô. Và ký tự DEL, với mọi bit đều 1, vốn ứng với cột thủng hết mọi ô. Hai ký tự vô nghĩa này không bao giờ xuất hiện trong các văn bản của thời đại mới. Và "mới" là lúc ngôn ngữ lập trình C ra đời. Nửa thế kỷ đã trôi qua, thực tế đó vẫn bất di bất dịch.

    Trở lại bài tập. Gọi E() là công thức (hàm) mã hóa một ký hiệu từ tập q giá trị {0, 1, 2,..., q - 1}. Khác với các cách mã hóa thường gặp, nó không thể chỉ phụ thuộc 1 biến, mà cần 2 biến: a, ký hiệu thứ k+1 cần mã hóa, và y, đoạn bản mã độ dài k đã mã hóa đoạn nguyên bản x cùng độ dài.

    Vì tính hữu hiệu, E(a,y) tuy nhiên không nên lệ thuộc vào cả xâu y mà chỉ nên lệ thuộc vào b, ký hiệu cuối của y, nếu có. Chỉ giới hạn tìm kiếm các công thức hữu hiệu như thế, có thể tách E(a,y) thành 2 công thức ứng với 2 trường hợp y trống và y không trống. Nghĩa là công thức cần tìm có dạng E1(a) và E2(a,b) thỏa yêu cầu của đề bài, là E2(a,b) != b nếu a != 0. Ở đây, 0 là giá trị ký hiệu bị cấm trong xâu nguyên bản (C-string), gọi là xâu mở, vì ký hiệu này đã được dành riêng để đóng xâu, nghĩa là đánh dấu hết xâu; và xâu có nó ở cuối, tính luôn cả nó, đương nhiên, gọi là xâu đóng.

    Dễ thấy rằng chỉ còn một lựa chọn duy nhất để mã hoá ký hiệu 0, là E2(0,b) = b. Vậy, nếu nguyên bản đóng thì bản mã có ký hiệu cuối (ở vị trí tương ứng với ký hiệu 0 cuối nguyên bản) lặp lại ký hiệu đứng trước nó. Đương nhiên, ký hiệu cuối này được gọi là ký hiệu đóng, xâu mã tính cả ký hiệu đóng được gọi là đóng và xâu mã không có ký hiệu ấy gọi là mở. Để xác định nốt trường hợp ký hiệu đầu được mã hóa sao, xâu trống được mã hóa sao, ta cần chỉ rõ công thức E1(). Nó không bị ràng buộc bởi bất cứ yêu cầu nào, nên để lập trình đơn giản, ta có thể chọn E1(a) = E2(a,0). Từ đó, ta biết E1(0) = 0.

    Mã nguồn đã chọn E1() đúng như trên, và đã chọn E2() như sau.

    Cách thứ nhất
    Code:
    E2(a,b) = a  khi a != b
    E2(a,b) = 0  khi a = b
    Cách thứ hai
    Code:
    E2(a,b) = a + b (mod q)
    Dễ thấy rằng cả hai cách đều cho

    Code:
    E1(a) = a
    Bỏ qua sai khác về cách chọn E1() và E2(), cách mã hóa là duy nhất.

    Nhắc lại, khác C-string vốn được đóng bằng 0, xâu mã được đóng bằng một ký hiệu lắp lại ký hiệu đứng ngay trước nó, nghĩa là có thể nhận cả những giá trị khác 0. Hơn nữa, tập ký hiệu của C-string mở chỉ có q - 1 giá trị, còn đối với xâu mã mở, dù mỗi ký hiệu cũng chỉ có thể nhận một trong số q - 1 giá trị, nhưng tập ký hiệu vẫn phải có q giá trị. Vậy, xâu mã không phải là C-string. Nó có một định dạng khác, mà mình đã đặt tên và nhắc tên ấy nhiều lần trước đây, nhưng chưa hề định nghĩa, là A-string. Hàm E1 và E2, bỏ qua công thức cụ thể, là một định nghĩa khả dĩ.

    Với yêu cầu nâng cao, không có trong đề bài nguyên thủy, rằng bản mã cũng phải là C-string, giải pháp là bảo toàn (không mã hóa) ký hiệu 0 (NUL), dành nó cho việc đóng bản mã. Vậy, tập ký hiệu cho bản mã chỉ còn 255 giá trị (thay vì 256). Nghĩa là tập ký hiệu của nguyên bản mở chỉ còn 254 giá trị. Nghĩa là bài toán mới này chỉ giải được nếu có một ký hiệu khác NUL không bao giờ xuất hiện trong nguyên bản. Ta đã biết ký hiệu như thế tồn tại, đó chính là DEL.

    Ở đây, tập ký hiệu không bắt đầu từ 0 mà bắt đầu từ 1, và giá trị ký hiệu bị cấm không phải là 0 mà là DEL = 127, nên các công thức cũng cần phải được sửa lại một cách tương ứng. Do DEL được giả thiết là không xuất hiện trong nguyên bản, nên ngộ nhỡ nó xuất hiện thì, đương nhiên, nó chỉ có thể được hiểu theo một cách duy nhất: nó là một ký hiệu đóng xâu [nguyên bản] và, như thế, chỉ có duy nhất một cách mã hoá nó, là lặp lại ký hiệu trước đó trong bản mã. Việc đóng này tất nhiên là không cần thiết bởi vì dù mở hay đóng bằng DEL thì sau đó nó vẫn có thể được đóng một lần nữa bằng NUL. Tất nhiên, cả việc đóng xâu bằng NUL cũng là không nhất thiết: chúng ta không bao giờ giả thiết dữ liệu là xâu đóng. Hàm xử lý dữ liệu, encodedecode, đều biết độ dài tối đa cho phép của dữ liệu. Chúng đóng bản mã khi và chỉ khi nguyên bản đóng trong phạm vi độ dài này.

    Với mọi ký hiệu được định nghĩa rõ ràng như thế, mọi chuỗi byte bất kỳ đều mã hoá được và giải mã được. Đó là lý do vì sao test2 lại thực hiện trên một mảng byte ngẫu nhiên và gọi encode hay decode nhiều lần, theo một thứ tự ngẫu nhiên.

    Trong ngữ cảnh của bài tập này, việc đóng xâu là vô nghĩa bởi vì ký hiệu đóng bản mã, do lặp lại ký hiệu đi trước, không bao giờ truyền được đến tay người ngoài hành tinh. Vậy, yêu cầu các ký hiệu của bản mã "không lắp lại ký hiệu trước" thật ra chỉ áp dụng lên xâu mở và đề bài đã được lập trình để kiểm thử chính xác như thế. Bản chất của bài tập, do thế, vẫn là dùng tập hợp q ký tự mã hoá một văn bản trên bảng q - 1 chữ cái.

    Cuối cùng, không phải chỉ gửi ra ngoài hành tinh, ngay trên Trái Đất, cách mã hoá này cũng rất phổ biến. Thí dụ, trong thông tin liên lạc, mã Morse có 2 ký hiệu âm thanh tịch (dấu chấm) và (dấu gạch) nhưng thực ra còn phải dùng thêm một ký hiệu thứ ba là lặng (dấu cách) để phân cách chúng, và hybrid ternary code mã hoá một chuỗi bit bằng 3 điện thế -1, 0 và +1 sao cho bit sau luôn có điện thế khác bit trước.
    Đã được chỉnh sửa lần cuối bởi Ada : 02-04-2021 lúc 11:49 PM.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn