ตั้งค่าการอ่าน

ค่าเริ่มต้น

  • เลื่อนอัตโนมัติ
    รวมโจทเขียนโปรแกรม พร้อม Code เฉลย

    ลำดับตอนที่ #2 : โจท การ Encrypt(เข้ารหัส) Binary String

    • อัปเดตล่าสุด 27 มิ.ย. 57


    Problem Statement
        

    สมมุติว่าเรามี binary string ดังนี้:

    011100011

    เป็นการเข้ารหัสแบบ One way โดยวิธีการเข้ารหัสจะใช้วิธี เพิ่มค่าของตัวเองจากตัวเลขที่อยู่ติดกัน.จากตัวอย่างของ Binary String ที่ว่ามาหลังจกเข้ารหัสแล้วจะได้เป็นแบบนี้:

    123210122

    หลังจากพิจารณาสมมุติเราให้ P เป็น Binary String อันเดิม และ Q เป็น Binary String ที่ผ่านการเข้ารหัสแล้วQ[i] = P[i-1] + P[i] + P[i+1] สำหรับตัวอักษรในทุกตำแหน่ง i. สำหรับที่ขอบของ String ที่ไม่มีตัวอักษร ให้แทนด้วย 0

    Binary String ที่เข้ารหัสแล้ว เราสามารถถอดรหัสโดยใช้วิธีได้ดังนี้ (ใช้ 123210122 เป็นตัวอย่าง):

    1. สมมุติให้ P[0] = 0.
    2. เพราะ Q[0] = P[0] + P[1] = 0 + P[1] = 1, แล้วเราก็รู้ว่า P[1] = 1.
    3. เพราะ Q[1] = P[0] + P[1] + P[2] = 0 + 1 + P[2] = 2, แล้วเราก็รู้ว่า P[2] = 1.
    4. เพราะ Q[2] = P[1] + P[2] + P[3] = 1 + 1 + P[3] = 3, แล้วเราก็รู้ว่า P[3] = 1.
    5. ทำซ้ำไปเรื่อยๆแล้วเราก็จะได้ว่า[4] = 0, P[5] = 0, P[6] = 0, P[7] = 1, และ P[8] = 1.
    6. และเราก็ตรวจคำตอบโดย Q[8] = P[7] + P[8] = 1 + 1 = 2. ดังที่เห็นพบว่าสมการใช้ได้และเราก็สามารถถอดรหัสได้

    แล้วเราก็ทำแบบเดิมอีกครั้งโดยสมมุติ P[0] ไหม่:

    1. สมมุติ P[0] = 1.
    2. เพราะ Q[0] = P[0] + P[1] = 1 + P[1] = 1, แล้วเราก็รู้ว่า P[1] = 0.
    3. เพราะ Q[1] = P[0] + P[1] + P[2] = 1 + 0 + P[2] = 2, แล้วเราก็รู้ว่า P[2] = 1.
    4. แล้วเราก็รพบว่า Q[2] = P[1] + P[2] + P[3] = 0 + 1 + P[3] = 3, ไม่ว่ายังไงเราก็ได้คำตอบว่าไม่ว่าทำยังไงก็จะได้ P[3] = 2.เสมอ จากข้อมูลที่ได้มันผิดพลาดเพราะ Binary String ที่ยังไม่เข้ารหัสต้องมีเฉพาะ  '0' หรือ '1' เสมอ ดังนั้น Binary String P จึงไม่มีคำตอบที่เป็นไปได้กรณีที่เริ่มต้นด้วย '1'.

    สำหรับโจทข้อนี้ ไม่มีวิธีถอดรหัสโดยใช้วิธีอื่น ดังนั้นให้ใช้วิธีที่กล่าวมาเท่านั้น

    สำหรับคำตอบที่ได้ ต้องคืนค่ามาเป็น String[] (อาเรย์ของสตริง) สำหรับกรณีที่ไม่สามารถหาคำตอบได้ให้คืนค่า "์NONE" จากตัวอย่าง ต้องคืนค่ามาแบบนี้ {"011100011", "NONE"}.

    Definition
        
    Class: BinaryCode
    Method: decode
    Parameters: String
    Returns: String[]
    Method signature: String[] decode(String message)
    (อย่าลืมทำให้ method เป็น public ด้วยนะ)

     

    ข้อจำกัด
    - message จะต้องสามารถรองรับตัวอักษรตั้งแต่ 1 ถึง 50 ตัวอักษร.
    - ทุกๆตัวอักษรสามารถ จะเป็นได้ทั้ง '0', '1', '2', หรือ '3'.

    ตัวอย่างข้อมูลที่ไส่เข้าไป และคืนค่ากลับมาอย่างถูกต้อง
    0)  
         
    "123210122"
    		 
    Returns: { "011100011",  "NONE" }
     
    1)  
         
    "11"
    		 
    Returns: { "01",  "10" }
     
    2)  
         
    "22111"
    		 
    Returns: { "NONE",  "11001" }
     
    3)  
         
    "123210120"
    		 
    Returns: { "NONE",  "NONE" }
     
    4)  
         
    "3"
    		 
    Returns: { "NONE",  "NONE" }
     
    5)  
         
    "12221112222221112221111111112221111"
    		 
    Returns: 
{ "01101001101101001101001001001101001",
  "10110010110110010110010010010110010" }

    คำตอบ Version 1 ที่ผมทำ ได้คะแนน 90/300 T^T คะแนนทำร้ายจิตใจมาก เดี๋ยวถ้าผมสามารถทำและได้คะแนนมากกว่านี้ แล้วจะเอามาโพสไหม่ครับ
    public class BinaryCode {
    public String[] decode(String message){
    String regex1 = "^[^3].*";
    String regex2 = "[0-3]{1,50}";
    String regex3 = ".*[^3]$";
    String regex4 = ".*(33).*";
    String[] ret_string=new String[2];
    ret_string[0]="NONE";
    ret_string[1]="NONE";
    if(!message.matches(regex4)&&message.matches(regex1)&&message.matches(regex2)&&message.matches(regex3)){
    // Assume P[0] = 0
    boolean decode_flag=false;
    int pevP1=0;
    int pevP2=0;
    int s_lenght=message.length();
    if (s_lenght>3) {
    String true_dat1="0";
    int p1=Character.getNumericValue(message.charAt(0))-pevP1;
    pevP2=p1;
    true_dat1=true_dat1+p1;
    int cur_p=0;
    for(int i=1;i<(s_lenght-2);i++){
    cur_p=Character.getNumericValue(message.charAt(i))-(pevP1+pevP2);
    pevP1=pevP2;
    pevP2=cur_p;
    true_dat1=true_dat1+cur_p;
    //System.out.println(i+" "+true_dat1);
    if(cur_p>1||cur_p<0||pevP2>1||pevP2<0){
    decode_flag=true;
    break;
    }
    }
    int lastP=Character.getNumericValue(message.charAt((s_lenght-1)))-pevP2;
    true_dat1=true_dat1+lastP;
    if(cur_p>1||cur_p<0||pevP2>1||pevP2<0||lastP>1||lastP<0){
    decode_flag=true;
    }
    if(!decode_flag){
    ret_string[0]=true_dat1;
    }
    // Assume P[0] = 1
    decode_flag=false;
    pevP1=1;
    pevP2=0;
    String true_dat2="1";
    p1=Character.getNumericValue(message.charAt(0))-pevP1;
    pevP2=p1;
    true_dat2=true_dat2+p1;
    cur_p=0;
    for(int i=1;i<(s_lenght-2);i++){
    cur_p=Character.getNumericValue(message.charAt(i))-(pevP1+pevP2);
    pevP1=pevP2;
    pevP2=cur_p;
    true_dat2=true_dat2+cur_p;
    //System.out.println(i+" "+true_dat2);
    if(cur_p>1||cur_p<0||pevP2>1||pevP2<0){
    decode_flag=true;
    break;
    }
    }
    lastP=Character.getNumericValue(message.charAt((s_lenght-1)))-pevP2;
    true_dat2=true_dat2+lastP;
    if(cur_p>1||cur_p<0||pevP2>1||pevP2<0||lastP>1||lastP<0){
    decode_flag=true;
    }
    if(!decode_flag){
    ret_string[1]=true_dat2;
    }
    }else if(s_lenght==2){
    // Assume P[0] = 0
    if(message.equals("00")||message.equals("11")){
    String true_dat1="0";
    int p1=Character.getNumericValue(message.charAt(0))-pevP1;
    pevP2=p1;
    true_dat1=true_dat1+p1;
    if(pevP2>1||pevP2<0){
    decode_flag=true;
    }
    if(!decode_flag){
    ret_string[0]=true_dat1;
    }
    // Assume P[0] = 1
    decode_flag=false;
    pevP1=1;
    pevP2=0;
    String true_dat2="1";
    p1=Character.getNumericValue(message.charAt(0))-pevP1;
    pevP2=p1;
    true_dat2=true_dat2+p1;
    if(pevP2>1||pevP2<0){
    decode_flag=true;
    }
    if(!decode_flag){
    ret_string[1]=true_dat2;
    }
    }
    }else if(s_lenght==1){
    int number=Character.getNumericValue(message.charAt(0));
    if(number==0){
    ret_string[0]="0";
    }else if(number==1){
    ret_string[1]="1";
    }else{
    ret_string[0]="NONE";
    ret_string[1]="NONE";
    }
    }else if(s_lenght==3){
    String true_dat1="0";
    int p1=Character.getNumericValue(message.charAt(0))-pevP1;
    pevP2=p1;
    true_dat1=true_dat1+p1;
    int lastP=Character.getNumericValue(message.charAt((s_lenght-1)))-pevP2;
    true_dat1=true_dat1+lastP;
    if(pevP2>1||pevP2<0||lastP>1||lastP<0){
    decode_flag=true;
    }
    if(!decode_flag){
    ret_string[0]=true_dat1;
    }
    // Assume P[0] = 1
    decode_flag=false;
    pevP1=1;
    pevP2=0;
    String true_dat2="1";
    p1=Character.getNumericValue(message.charAt(0))-pevP1;
    pevP2=p1;
    true_dat2=true_dat2+p1;
    lastP=Character.getNumericValue(message.charAt((s_lenght-1)))-pevP2;
    true_dat2=true_dat2+lastP;
    if(pevP2>1||pevP2<0||lastP>1||lastP<0){
    decode_flag=true;
    }
    if(!decode_flag){
    ret_string[1]=true_dat2;
    }
    }
     
    }
    return ret_string;
    }
     
    }

    โคต V2 คะแนนเท่าเดิม T^T แต่เวลาการประมวลผล น้องลง จาก 0.008วิ เหลือ 0.005 วินาที
     
    public class BinaryCode {
    public String[] decode(String message){
    String[] ret_string=new String[2];
    ret_string[0]="0";
    ret_string[1]="1";
    int s_lenght=message.length();
    int[] q= new int[s_lenght];
    int[] p0= new int[s_lenght];
    p0[0]=0;
    int[] p1= new int[s_lenght];
    p1[0]=1;
    for(int i=0;i<s_lenght;i++){
    q[i]=Character.getNumericValue(message.charAt(i));
    }
    if(s_lenght==1){
    int number=Character.getNumericValue(message.charAt(0));
    if(number==0){
    ret_string[0]="0";
    }else if(number==1){
    ret_string[1]="1";
    }else{
    ret_string[0]="NONE";
    ret_string[1]="NONE";
    }
    }else if(s_lenght>=2){
    //Assume 0
    for(int i=1;i<s_lenght;i++){
    if(i==1){
    p0[i]=q[i-1]-p0[i-1];
    }else{
    p0[i]=q[i-1]-p0[i-1]-p0[i-2];
    }
    //System.out.println(p0[i]);
    if(p0[i]>1||p0[i]<0){
    ret_string[0]="NONE";
    break;
    }else{
    ret_string[0]+=p0[i];
    }
    }
    //System.out.println(ret_string[0]+"   "+ret_string[1]);
    //Assume 1
    for(int i=1;i<s_lenght;i++){
    if(i==1){
    p1[i]=q[i-1]-p1[i-1];
    }else{
    p1[i]=q[i-1]-p1[i-1]-p1[i-2];
    }
    //System.out.println(p1[i]);
    if(p1[i]>1||p1[i]<0){
    ret_string[1]="NONE";
    break;
    }else{
    ret_string[1]+=p1[i];
    }
    }
    //System.out.println(ret_string[0]+"   "+ret_string[1]);
    }
    //System.out.println(ret_string[0]+"   "+ret_string[1]);
    return check_decode(ret_string,p0,p1,q,s_lenght);
    }
    String[] check_decode(String[] ret_string,int[] p0,int[] p1,int[] q,int s_lenght){
    s_lenght-=1;
    if(!ret_string[0].equals("NONE")&&s_lenght>0){
    boolean flag=q[s_lenght]==p0[s_lenght-1]+p0[s_lenght];
    if(!flag){
    ret_string[0]="NONE";
    }
    }
    if(!ret_string[1].equals("NONE")&&s_lenght>0){
    boolean flag=q[s_lenght]==p1[s_lenght-1]+p1[s_lenght];
    if(!flag){
    ret_string[1]="NONE";
    }
    }
    return ret_string;
     
    }
     
    }
     

    ติดตามเรื่องนี้
    เก็บเข้าคอลเล็กชัน

    ผู้อ่านนิยมอ่านต่อ ดูทั้งหมด

    loading
    กำลังโหลด...

    อีบุ๊ก ดูทั้งหมด

    loading
    กำลังโหลด...

    ความคิดเห็น

    ×