0

p.s сортировка пузырьком и двоичный поиск нужны по заданию

Он выводит значения, которые находятся и в A, и в B, но нужно только которые находятся в Авведите сюда описание изображения

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
    
namespace TEST
{
    class Program
    {
        static int[] BubbleSort(int[] mas) //сортировка пузырьком, по заданию
        {
            int temp;
            for (int i = 0; i < mas.Length; i++)
            {
            for (int j = i + 1; j < mas.Length; j++)
                {
                    if (mas[i] > mas[j])
                    {
                        temp = mas[i];
                        mas[i] = mas[j];
                        mas[j] = temp;
                    }
                }
            }
            return mas;
        }

        static void Main(string[] args) //двоичный поиск, по заданию 
        {
            Stopwatch time = new Stopwatch();
            Random Rnd = new Random();
            int mas_size = 100, m, lowerBound, upperBound;
            int[] a = new int[mas_size];
            int[] b = new int[mas_size];
            int[] c = new int[mas_size];
            int last_zap = 0;
            for (int j = 0; j < a.Length; j++)
            {
                a[j] = Rnd.Next(0, 100);
                b[j] = Rnd.Next(0, 100);
            }
            time.Start();
            a = BubbleSort(a);
            b = BubbleSort(b);
            for (int j = 0; j < a.Length - 1; j++)
            {
                lowerBound = 0;
                upperBound = mas_size;
                if (last_zap > 0)
                {
                    if (c[last_zap - 1] == a[j])
                        continue;
                }

                while (last_zap < 100) //НАХОЖДЕНИЕ ЗНАЧЕНИЙ МАССИВА А, КОТОРЫХ НЕТ В МАССИВЕ Б
                {
                    m = (lowerBound + upperBound) / 2;
                    if (m >= mas_size)
                        break;
                    if (a[j] < b[m])
                        upperBound = m - 1;
                    else if (a[j] > b[m])
                        lowerBound = m + 1;
                    else
                    {
                        c[last_zap] = b[m];
                        last_zap++;
                        break;
                    }

                    if (lowerBound > upperBound || m == 0)
                        break;
                }
            }
            time.Stop(); //установить время работы программы, по заданию
            Console.WriteLine("Продолжительность работы: " + time.Elapsed);
            if (mas_size <= 100)
            {
                Console.WriteLine("");
                for (int j = 0; j < a.Length; j++)
                {
                    Console.Write("a[{0}] = {1};", j + 1, a[j]);
                    if (j % 10 == 9) Console.WriteLine();
                }
                Console.WriteLine();
                for (int j = 0; j < b.Length; j++)
                {
                    Console.Write("b[{0}] = {1};", j + 1, b[j]);
                    if (j % 10 == 9) Console.WriteLine();
                }
                if (last_zap > 0)
                {
                    Console.Write("\n Элементы, которые присутствуют в массиве А, но отсутствуют в массиве В:\n");
                    for (int j = 0; j < last_zap; j++)
                    {
                        { Console.Write(c[j] + " ");
                    }
                }
                else
                    Console.WriteLine("\n Не соответствуют условию\n");
            }
            Console.ReadLine();
        }
    }
}
7
  • А что не работает конкретно? Поиск не работает? Зачем Вам двоичный поиск? Он нужен для поиска индекса элемента.
    – Aarnihauta
    30 ноя 2021 в 9:38
  • 1
    //НАХОЖДЕНИЕ ЗНАЧЕНИЙ - индексов или самих значений? Текст задания в секрете?
    – aepot
    30 ноя 2021 в 9:53
  • Двоичный поиск требуется для задания, находим сами значения массива 30 ноя 2021 в 10:08
  • Для выполнения задания необходимо использовать два одномерных массива целых чисел А[M] и В[N] (М и N – произвольные целые числа, не превышающие 2^14). Инициализируйте исходные массивы данными, после чего отсортируйте массивы с использованием алгоритма, указанного в вашем задании. Создайте одномерный массив С, который содержит элементы, отвечающие условию задания, в одном экземпляре (без повторений). Сравните время работы программы при следующих размерах исходных массивов: 100, 1000, 5000, 10000, 15000 элементов. 30 ноя 2021 в 10:09
  • Задание: элементы, которые присутствуют в массиве А, но отсутствуют в массиве В. Алгоритм сортировки: пузырьком. Алгоритм поиска: двоичный 30 ноя 2021 в 10:11

2 ответа 2

0

Выделите бинарный поиск в отдельную функцию. Возьмите такую его реализацию, которая возвращает индекс вставки элемента

пример

Если на шарп перевести, будет примерно так:

//l == r == искомый индекс
//Если искомого элемента не было в массиве,
//бинарный поиск найдёт следующий после него элемент.
static int binsearch_array(int[] a, int val, int l, int r) {

   while (r > l) {
        int m = (l + r) / 2;    //целочисленное деление!

        if (a[m] < val) {
            l = m + 1;
        } else if (a[m] > val) {
            r = m - 1;
        } else {
            return m;
        }
    }
    return l;
 }

Получив индекс, сравните значение с элементом по этому индексу. Если не равны, то значение отсутствует, и следующий бинарный поиск начинайте именно с этого индекса (при сортированном первом массиве).

0
0
    using System;
    using System.Collections.Generic;
    using System.Text;
    using System.Threading.Tasks;
    using System.Diagnostics;
    namespace TEST
    {
        class Program
        {
        static int[] BubbleSort(int[] mas) //сортировка пузырьком
        {
            int temp;
            for (int i = 0; i < mas.Length; i++)
            {
            for (int j = i + 1; j < mas.Length; j++)
                {
                    if (mas[i] > mas[j])
                    {
                        temp = mas[i];
                        mas[i] = mas[j];
                        mas[j] = temp;
                    }
                }
            }
            return mas;
        }
        static void Main(string[] args) //двоичный поиск, по заданию 
        {
            Stopwatch time = new Stopwatch();
            Random Rnd = new Random();
            int mas_size = 10, m, lowerBound, upperBound;
            int[] a = new int[mas_size];
            int[] b = new int[mas_size];
            int[] c = new int[mas_size];
            int last_zap = 0;
            for (int j = 0; j < a.Length; j++)
            {
                a[j] = Rnd.Next(0, 100);
                b[j] = Rnd.Next(0, 100);
            }
            time.Start();
            a = BubbleSort(a);
            b = BubbleSort(b);
            for (int j = 0; j < a.Length - 1; j++)
            {
                lowerBound = 0;
                upperBound = mas_size;
                if (last_zap > 0)
                {
                    if (c[last_zap - 1] == a[j])
                        continue;
                }
 
                while (true) //проблемная часть
                {
                    m = (lowerBound + upperBound) / 2;
                    if ((m < 0) || (m > mas_size - 1))
                        break;
                    if (a[j] < b[m])
                        upperBound = upperBound - 1;
                    else if (a[j] > b[m])
                        lowerBound = lowerBound + 1;
                    else
                    {
                        break;
                    }
 
                    if (lowerBound > upperBound || m == 0)
                    {
                        c[last_zap] = a[j];
                        last_zap++;
                        break;
                    }
                }
            }
            time.Stop(); //установить время работы программы, по заданию
            Console.WriteLine("Продолжительность работы: " + time.Elapsed);
            if (mas_size <= 10)
            {
                Console.WriteLine("");
                for (int j = 0; j < a.Length; j++)
                {
                    Console.Write("a[{0}] = {1};", j + 1, a[j]);
                    if (j % 10 == 9) Console.WriteLine();
                }
                Console.WriteLine();
                for (int j = 0; j < b.Length; j++)
                {
                    Console.Write("b[{0}] = {1};", j + 1, b[j]);
                    if (j % 10 == 9) Console.WriteLine();
                }
                if (last_zap > 0)
                {
                    Console.Write("\n Элементы, которые присутствуют в массиве А, но отсутствуют в массиве В:\n");
                    for (int j = 0; j < last_zap; j++)
                    {
                        if (c[j] != 0) { Console.Write(c[j] + " "); };
                    }
                }
                else
                    Console.WriteLine("\nНе соответствуют условию\n");
            }
            Console.ReadLine();
        }
    }
     static void Main(string[] args) //двоичный поиск, по заданию 
        {
            Stopwatch time = new Stopwatch();
            Random Rnd = new Random();
            int mas_size = 10, m, lowerBound, upperBound;
            int[] a = new int[mas_size];
            int[] b = new int[mas_size];
            int[] c = new int[mas_size];
            int last_zap = 0;
            for (int j = 0; j < a.Length; j++)
            {
                a[j] = Rnd.Next(0, 100);
                b[j] = Rnd.Next(0, 100);
            }
            time.Start();
            a = BubbleSort(a);
            b = BubbleSort(b);
            for (int j = 0; j < a.Length - 1; j++)
            {
                lowerBound = 0;
                upperBound = mas_size;
                if (last_zap > 0)
                {
                    if (c[last_zap - 1] == a[j])
                        continue;
                }
 
                while (true) //проблемная часть
                {
                    m = (lowerBound + upperBound) / 2;
                    if ((m < 0) || (m > mas_size - 1))
                        break;
                    if (a[j] < b[m])
                        upperBound = upperBound - 1;
                    else if (a[j] > b[m])
                        lowerBound = lowerBound + 1;
                    else
                    {
                        break;
                    }
 
                    if (lowerBound > upperBound || m == 0)
                    {
                        c[last_zap] = a[j];
                        last_zap++;
                        break;
                    }
                }
            }
            time.Stop(); //установить время работы программы, по заданию
            Console.WriteLine("Продолжительность работы: " + time.Elapsed);
            if (mas_size <= 10)
            {
                Console.WriteLine("");
                for (int j = 0; j < a.Length; j++)
                {
                    Console.Write("a[{0}] = {1};", j + 1, a[j]);
                    if (j % 10 == 9) Console.WriteLine();
                }
                Console.WriteLine();
                for (int j = 0; j < b.Length; j++)
                {
                    Console.Write("b[{0}] = {1};", j + 1, b[j]);
                    if (j % 10 == 9) Console.WriteLine();
                }
                if (last_zap > 0)
                {
                    Console.Write("\n Элементы, которые присутствуют в массиве А, но отсутствуют в массиве В:\n");
                    for (int j = 0; j < last_zap; j++)
                    {
                        if (c[j] != 0) { Console.Write(c[j] + " "); };
                    }
                }
             else        
                    Console.WriteLine("\nНе соответствуют условию\n");
            }
            Console.ReadLine();
        }
    }
}
1
  • 1
    А что это за фрагмент неотформатированного кода, что он делает?
    – 0xdb
    30 ноя 2021 в 17:20

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.