من رفتم سربازی اگر محتوای منو دوست داشتید و بدردتون خورد از من حمایت مالی کنید

تمرین طول سیم

تمرین طول سیم
تمرین طول سیم

تمرین طول سیم

یکی از زیباترین مسائل برنامه نویسی در مباحث ساختمان داده‌ها تمرین “طول سیم” است که برای اولین بار در دوران دانشجویی بنده هم این سوال مطرح شده بود.

 

تمرین طول سیم

طول سیم

تعداد n خانه در نقاط صحیح مختصات قرار دارند. می‌خواهیم بین هر دو خانه یک سیم تلفن بکشیم. میزان سیم مورد نیاز برای وصل کردن دو خانه به اندازه‌ی فاصله‌ی منهتن آن‌ها است. برنامه‌ای بنویسید که طول بزرگترین سیم موردنیاز را پیدا کند.

ورودی

در خط اول ورودی ابتدا عدد n داده می‌شود. سپس در n خط بعد در هر خط دو عدد که نشان‌دهنده‌ی مختصات خانه‌ی iام است داده می‌شود.

خروجی

طول بزرگترین سیم مورد استفاده را چاپ کنید.

محدودیت‌ها

این محدودیت‌ها باید جز بخش‌های کنترلی برنامه بماند.

۱ ≤ n ≤ ۱۰۰۰۰۰
-۱۰۰۰۰۰۰ ≤ Xi,Yi ≤ ۱۰۰۰۰۰۰

مثال:

خروجی نمونه:

۵ 
۲ ۲ 
۴ ۶ 
۳ ۸ 
۹ ۲ 
۵ ۵

خروجی نمونه:

۱۲

حل تمرین

کلاس File:

این کلاس وظیفه دریافت اطلاعات از ورودی و انتقال آنها به خروجی را دارد و علت نام‌گذاری آن با نام کلاس File این موضوع است. داده‌های ورودی خروجی در این تمرین توسط فایل‌های متنی منتقل خواهند شد.

import java.io.*;

public class File
{
    private String input_path;
    private String output_path;

    public File()
    {
        this.input_path = "d://input.txt";
        this.output_path = "d://output.txt";
    }
    public String[] read() throws IOException
    {
        FileInputStream input = null;
        String[] data=null;
        int i=0;
        int array_bound=100000;
        try{
            input = new FileInputStream(input_path);
            DataInputStream dataInputStream = new DataInputStream(input);
            BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(dataInputStream));
            String strLine;
            while ((strLine=bufferedReader.readLine()) != null)
            {
                if(data==null)
                {
                    if(Integer.parseInt(strLine)<=100000)
                        array_bound = Integer.parseInt(strLine);
                    data = new String[array_bound];
                    continue;
                }
                else if(i==array_bound)
                {
                    break;
                }
                data[i] = strLine + (char) 13 + (char) 10;
                i += 1;
            }
        }
        finally
        {
            if(input == null)
            {
                input.close();
            }
        }
        return data;
    }
    public void write(String data, boolean append) throws IOException
    {
        BufferedWriter output = null;
        try
        {
            output = new BufferedWriter(new FileWriter(output_path, append));
            if(data==null)
                output.write("");
            else
                output.write(data + (char) 13 + (char) 10);
            output.close();
        }
        finally
        {
            if(output == null)
            {
                output.close();
            }
        }
    }
}

کلاس LenghtWire:

در واقع کلاس اصلی برنامه‌ی ما این کلاس است که در آن توابع اصلی برنامه و منطق روی آن پیاده شده است.

import com.sun.org.apache.xalan.internal.xsltc.dom.AbsoluteIterator;

public class LengthWire
{
    private int home_bound;
    private int counter;
    private int[][] home;
    private int abs(int number)
    {
        return Math.abs(number);
    }

    LengthWire()
    {
        counter = 0;
        home_bound=100000;
        home = new int[home_bound][2];
    }
    public void setHome(int x, int y)
    {
        if(x>1000000 || x<-1000000)
            return;
        else if(y>1000000 || y<-1000000)
            return;
        home[counter][0] = x;
        home[counter][1] = y;
        counter+=1;
    }
    public int calculate()
    {
        int result=0;
        int max=0;
        for (int i=0; i<=counter; i++)
        {
            for(int j=i; j<=counter; j++)
            {
                result = abs(home[i][0] - home[j][0]) + abs(home[i][1] - home[j][1]);
                if(result>=max)
                {
                    max = result;
                }
            }
        }
        return max;
    }
}

کلاس Main:

این کلاس توسط مفسر زبان برنامه‌نویسی جاوا به عنوان اولین کلاس اجرا خواهد شد علت این موضوع هم وجود تابع public static void main است. این تابع وظیفه‌ی اتصال توابع File و LenghtWire را به هم دارد.

import java.io.*;

public class Main
{
    public static void main(String[] args)  throws IOException
    {
        File file = new File();
        file.write(null , false);
        LengthWire lengthwire = new LengthWire();
        String[] construction = file.read();
        String[] job = new String[2];
        int j;
        String result;

        for (String my_construction:construction)
        {
            j=0;
            job[0]="";
            job[1]="";
            for (int i = 0; i < my_construction.length(); i++)
            {
                if (!Character.isWhitespace(my_construction.charAt(i)))
                {
                    job[j] += String.valueOf(my_construction.charAt(i));
                }
                else
                {
                    j+=1;
                    if(j>1)
                        break;
                }
            }
            lengthwire.setHome(Integer.parseInt(job[0]), Integer.parseInt(job[1]));
        }
        result = String.valueOf(lengthwire.calculate());
        System.out.println(result);
        file.write(result, false);
    }
}

در صورت وجود هر سوالی از بخش نظرات امکان پرسش سوال خود را دارید.

منبع سوال سایت quera.ir هست ولی این مسئله به صورت اختصاصی توسط camelcase.ir حل شده است.

برای پیشنهاد حل مسئله توسط ما می‍‌توانید از بخش نظرات آدرس سوال یا متن سوال را فرستاده و در صورت امکان به آن سوال پاسخگویی خواهد شد.

در صورتی که علاقه به مشارکت دارید می‌توانید این مسئله را با زبان‌های دیگر برنامه نویسی حل کرده و برای ما ارسال کنید تا با نام شما برای دیگران به اشتراک بگذاریم.

برای امتیاز به این نوشته کلیک کنید!
[کل: 0 میانگین: 0]