طراحی سایت و برنامه نویسی

آموزش طراحی سایت و برنامه نویسی

طراحی سایت و برنامه نویسی

آموزش طراحی سایت و برنامه نویسی

قالب‌های گیت هاب برای درخواست‌های Pull یکپارچه و هوشمندانه — راهنمای کاربردی

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

مشکلات رایج

اگر تاکنون به عنوان یک توسعه‌دهنده نرم‌افزار با گیت‌هاب کارکرده باشید، چه این کار را به صورت انفرادی انجام داده باشید و چه بخشی از یک تیم بوده باشید، احتمالاً با مشکلاتی که در ادامه معرفی خواهیم کرد آشنا هستید.

درج پیام‌های کامیت خیلی کوتاه

نخستین مشکل رایج پیام کامیت بی‌معنی است. این پیام‌ها عموماً چندین بار ارسال می‌شوند، چون ما توسعه‌دهندگان تنبلی هستیم و عادت داریم تغییرات مختلف را با پیام‌های یکسانی به گیت‌هاب پوش کنیم و هیچ توجه نداریم که آن تغییرات هیچ ارتباطی با پیام مربوطه ندارند.

قالب های گیت هاب

نکته: اگر می‌خواهید برخی پیام‌های کامیت جالب و سرگرم‌کننده را بخوانید، سری به این وب‌سایت (+) بزنید. با رفرش کردن صفحه پیام‌های کامیت عجیب‌وغریبی را مشاهده خواهید کرد.

درخواست‌های Pull کاملاً معماگونه

احتمالاً یک درخواست pull مانند درخواست زیر را در یک ریپو دیده‌اید (و یا ارسال کرده‌اید). تلاش نکنید انکار کنید! نام و جزییات جهت حفظ حریم خصوصی پنهان شده‌اند:

تصویر فوق یک درخواست pull واقعی روی گیت‌هاب است و پیام‌های کامیت فراوانی دارد که معنی بسیار کمی دارند و برای کسی که به آن‌ها نگاه می‌کند جزییات چندانی از آنچه در حال اتفاق افتادن است ارائه نمی‌کنند.

در این مرحله، ممکن است با خود فکر کنید، این کار در واقع شبیه همان کاری است که خودتان قبلاً دیده‌اید (انجام داده‌اید) و مشکل چندانی ایجاد نمی‌کند.

اگر یک توسعه‌دهنده منفرد هستید که روی پروژه شخصی خود کار می‌کنید، همواره از همه چیز در کدبیس اطلاع دارید و شاید حق با شما باشد. اما اگر در حال کار با تیمی متشکل از 10 یا 20 توسعه‌دهنده دیگر هستید و یک اپلیکیشن می‌سازید که از سوی صدها یا هزاران نفر استفاده می‌شود و توسعه‌دهندگان دیگر باید تغییراتی که شما ایجاد کرده‌اید را ببینند و تشخیص دهند که کد منطقی است یا نه و در ادامه هیچ مشکلی در شاخه master کد ایجاد نمی‌کند، در این صورت با یک مشکل بسیار بزرگ مواجه هستیم.

راه‌حل‌ها

برای حل این مشکل‌ها چند راه‌حل مختلف وجود دارند که ممکن است گذشته تجربه کرده باشید.

گزینه 1: فرایند کاملاً دستی

یک مجموعه نسبی از الزامات داریم که باید به هر درخواست pull جدید اضافه کنیم. این موارد چیزهایی مانند این هستند:

لینک‌هایی به روند قابلیتی که مشغول کار روی آن هستیم روی backlog.
لینک‌هایی به Jenkiks خودکار که شاخه ما بر مبنای آن ساخته شده و درون QA توزیع یافته است.
لینک‌هایی به شاخه قابلیت برای تست کردن.
گزارش پوشش کد
لینک‌های به PR-های مرتبط در ریپوهای دیگر و غیره.

این راه‌حل به درستی کار می‌کند، مگر این که افراد اضافه کردن یکی یا چند مورد از این لینک‌ها را فراموش کنند (یا به آن اهمیت ندهند) و یک سیستم صورت‌بندی برای اعضای جدید که به تیم ملحق می‌شوند نداشته‌ باشیم تا بدانند قالب PR-هایشان باید چگونه باشد.

گزینه 2: قالبی که باید کپی شده و هر بار در PR چسبانده شود

تلاش دوم ما کمی غیر دستی‌تر است. در این روش از یک قالب درخواست pull استفاده می‌شود که تیم می‌تواند در یک فایل txt. در اسلک نگهداری کند و آن را در یکی از کانال‌های تیم توسعه پین کند. ظاهر آن می‌تواند به صورت زیر باشد:

Story

Jira, Pivotal Tracker, (link to where the story you worked on lives)

PR Branch

URL to the automated branch build for feature testing

Code Coverage

URL to the automated code coverage report run during the automated build process

e2e

URL to the automated end to end tests run against the feature branch

UX Approved

yes / no

Newman

yes / no

Related PR’s

TBD

اما در این حالت هم اعضای تیم باید بروند و دنبال قالب بگردند، قالب‌بندی نشانه‌گذاری آن را کپی کنند و آن را درون همه درخواست‌های pull وارد کرده و محتوای آن را نیز پر کنند.

این گزینه بهتری محسوب می‌شود، زیرا دست‌کم قالب تضمین می‌کند که احتمال فراموش کردن موارد مختلف کمتر است، اما همچنان مستعد خطا است. در اغلب موارد افراد تیم به سراغ PR-های قدیمی می‌روند، آن را باز می‌کنند و محتوای آن را کپی کرده و در PR جدید می‌چسبانند. البته این کار اشکالی ندارد، اما گاهی افراد فراموش می‌کنند که لینک استوری را به‌روز کنند یا لینک سربه‌سر تست را درج نمی‌کنند و مشکل پیش می‌آید.

این بهترین راه‌حلی بود که اعضای تیم می‌توانستند داشته باشند تا این که برخی توسعه‌دهندگان تازه‌کار به تیم ما اضافه شدند. زمانی که راه‌حل بهینه خود یعنی قالب PR را که استفاده می‌کردیم به اعضای جدید تیم نشان دادیم، آن‌ها پرسیدند که چرا از قالب‌های گیت‌هاب استفاده نمی‌کنیم؟ پاسخ ما این بود که: «چون هیچ یک از ما تاکنون چیزی در مورد آن نشنیده‌ایم!» در نهایت بدین ترتیب با این مفهوم به شدت جالب و البته آسان آشنا شدیم.

گزینه 3: قالب‌های گیت‌ هاب؛ روش خودکار برای انجام درخواست Pull

این گزینه راه‌حل بهتری محسوب می‌شود و در واقع راه‌حلی است که هرکس باید استفاده کند. قالب‌های گیت‌هاب ابداع بسیار جالبی از سوی گیت‌هاب برای درخواست‌های pull و همچنین issue-ها محسوب می‌شوند. از آنجا که PR-ها دغدغه هر تیم توسعه‌ای هستند، به مستندات گیت‌هاب مراجعه کردیم تا در مورد آن بیشتر بدانیم:

زمانی که یک قالب درخواست pull به ریپازیتوری خود اضافه کنید، مشارکت‌کنندگان در پروژه به صورت خودکار محتوای قالب را در بدنه درخواست pull خود مشاهده خواهند کرد.

این همان چیزی است که هر تیم توسعه‌ای نیاز دارد. این روش تضمین می‌کند که همه درخواست‌های pull یک شکل هستند و لازم نیست اعضای تیم در مورد آن نگرانی داشته باشند. راه‌اندازی آن نیز بسیار آسان است.

راه‌اندازی قالب‌های گیت‌ هاب در یک پروژه

با این که راه‌اندازی یک قالب PR بسیار سرراست است، اما برای سهولت هر چه بیشتر در ادامه مراحل آن را توضیح داده‌ایم.

گام 1: افزودن یک پوشه /github. به ریشه پروژه

مستندات این بخش بیان می‌کنند که می‌توان یک قالب PR را در خود ریشه دایرکتوری پروژه یا در پوشه‌ای به نام /docs یا /github. اضافه کرد. از آنجا که ما می‌خواهیم پوشه PR را در اغلب موارد که مشغول توسعه هستیم نادیده بگیریم. تصمیم گرفتیم پوشه قالب را درون پوشه /github. بسازیم:

قالب های گیت هاب

گام 2: افزودن فایل نشانه‌گذاری pull_request_template.md درون پوشه

برای این که گیت‌هاب به صورت خودکار قالب‌بندی را از فایل نشانه‌گذاری برای قالب‌های PR بردارد، باید نام فایل را pull_request_template.md بگذارید. در ادامه نمونه‌ای از قالبی که تیم ما استفاده می‌کند را می‌بینید:

Tracker ID: #ADD LINK TO PIVOTAL STORY

Unit tests completed?: (Y/N)

PR Branch #ADD LINK TO PR BRANCH

Code Coverage & Build Info #ADD LINK TO JENKINS CONSOLE

E2E Approved #ADD LINK TO PASSING E2E TESTS

Windows Testing #HAS WINDOWS BEEN TESTED?

Related PR #ADD ANY RELATED PULL REQUESTS

UX Approved #ADD UX APPROVAL IF NEEDED

گام 3: افزودن این فایل‌ها به شاخه master و آماده‌سازی همه درخواست‌های PR

در ادامه تصویری از یک ریپازیتوری را می‌بینید که قالب درخواست PR به آن اضافه شده و یک درخواست pull نیز به عنوان نمونه ایجاد شده است:

قالب های گیت هاب

افزودن یک قالب PR استاندارد به هر ریپازیتوری دقیقاً به همین سادگی است.

سخن پایانی

زمانی که با تیمی از توسعه‌دهندگان سر و کار داریم که روی محصولی حساس مشغول کار هستند، درخواست‌های pull یک ضرورت حیاتی محسوب می‌شوند، اما به کمک امکان pull_request_templates در گیت‌هاب این مشکل می‌تواند به آسانی مرتفع شود.

مزیت‌های قالب‌های صورت‌بندی شده PR زیاد هستند، اما برخی از آن‌ها که می‌توان اشاره کرد میزان انعطاف‌پذیری آن‌ها است. مهم نیست که تیم شما چه چیزی را مورد بررسی و پذیرش قرار می‌دهد، یک درخواست Pull را می‌توان به سادگی در هر ریپازیتوری جای داده و پیاده‌سازی کرد. این همان نوع از سهولت کار توسعه‌دهنده‌ها است که برای صورت‌بندی موارد ضروری مانند PR-ها به آن نیاز داریم.

منبع: فرادرس

مشاوره جمعه 14 تیر 1398 ساعت 18:19

0 نظر

یادگیری ماشین در اندروید با ML Kit برای فایربیس — از صفر تا صد

آن روزها که استفاده از قابلیت‌های یادگیری ماشین تنها روی کلود امکان داشت و این مسئله نیازمند توان محاسباتی بالا، سخت‌افزار پیشرفته و مواردی از این دست بود، گذشته است. امروزه دستگاه‌های موبایل بسیار قدرتمندتر شده‌اند و الگوریتم‌های ما نیز کارایی بالاتری یافته‌اند. همه این موارد منجر به این نتیجه شده است که بهره‌گیری از یادگیری ماشین روی دستگاه‌های همراه امکان یافته است و دیگر صرفاً یک نظریه عملی-تخیلی محسوب نمی‌شود. در این نوشته به بررسی عملی یک پروژه یادگیری ماشین در اندروید با استفاده از ML Kit‌ برای «فایربیس» (Firebase) می‌پردازیم.

مقدمه

یادگیری ماشین امروزه روی دستگاه‌های گوناگون در همه جا استفاده می‌شود. نمونه‌هایی از این مسئله به شرح زیر هستند:

دستیار هوشمند: کورتانا، Siri و دستیار گوگل نمونه‌هایی از این دستیارها هستند. دستیار گوگل در کنفرانس IO امسال یک به‌روزرسانی عمده دریافت کرده است و عمده توجه بر روی افزایش ظرفیت‌های یادگیری ماشین آن روی دستگاه‌های همراه بوده است.
فیلترهای اسنپ‌چت: اسنپ‌چت از یادگیری ماشین برای تشخیص چهره‌های انسان و قرار دادن فیلترهای 3 بعدی مانند عینک، کلاه، و.. روی آن‌ها استفاده می‌کند.
پاسخ هوشمند: پاسخ هوشمند (Smart Replay) یک از قابلیت‌های بسیاری از دستگاه‌های امروزی است و در اپلیکیشن‌های چت مانند واتس اپ و غیره استفاده می‌شود؛ هدف آن ارائه پیغام‌های از پیش تعریف شده‌ای است که می‌توانید از آن‌ها را در پاسخ به پیام‌های دریافتی گوناگون خود بهره بگیرید.
گوگل لنز: با این که این سرویس همچنان در مراحل ابتدایی خود است، اما از مدل‌های یادگیری ماشین برای شناسایی و برچسب‌گذاری اشیا استفاده می‌کند.

این فهرست را می‌توان بسیار ادامه داد، بنابراین به این مقدار اکتفا می‌کنیم. در این مقاله به بررسی شیوه‌های استفاده از یادگیری ماشین در اپلیکیشن‌های اندروید و هوشمندتر ساختن آن‌ها می‌پردازیم.

ML Kit برای فایربیس چیست؟

ML Kit‌ برای فایربیس یک SDK موبایل است که گنجاندن ظرفیت‌های یادگیری ماشین در اپلیکیشن‌ها را برای توسعه‌دهندگان موبایل آسان‌تر ساخته است. این کیت شامل API های پیش‌ساخته زیر است:

بازشناسی متن: این API برای بازشناسی و استخراج متن از تصاویر استفاده می‌شود.
تشخیص چهره: برای تشخیص چهره و نشانه‌گذاری بخش‌های مختلف چهره همراه با مرزهای آن استفاده می‌شود.
تشخیص و ردگیری شیء: برای تشخیص، ردگیری و طبقه‌بندی اشیا در تصاویر دوربین و عکس‌های از پیش ثبت شده استفاده می‌شود.
برچسب‌گذاری تصویر: شناسایی اشیا، مکان‌ها، فعالیت‌ها، گونه‌های حیوانات و مواردی از این دست.
اسکن بارکد: برای اسکن و پردازش بارکدها استفاده می‌شود.
تشخیص مکان: برای شناسایی امکان معروف و شناخته شده در تصاویر به کار می‌رود.
شناسه زبان: برای تشخیص زبان یک متن استفاده می‌شود.
ترجمه روی دستگاه: متن نمایش داده شده روی یک دستگاه را از یک زبان به زبانی دیگر ترجمه می‌کند.
پاسخ هوشمند: پاسخ‌های متنی هوشمندانه‌ای بر مبنای پیام‌های قبلی تولید می‌کند.

ML Kit‌ در اصل و به زبان ساده، راهکاری است که با آن می‌توانید از پیچیدگی‌ها بهره‌گیری از یادگیری ماشین در اپلیکیشن‌های خود برای تلفن‌های هوشمند بکاهید.

چه چیزی خواهیم ساخت؟

ما در این مقاله از ظرفیت تشخیص چهره ML Kit‌ برای شناسایی چهره‌ها در یک تصویر استفاده می‌کنیم. بدین منظور تصاویر را از طریق دوربین می‌گیریم و اینترفیس را روی آن اجرا می‌کنیم.

برای استفاده از ML Kit‌ لازم است که یک حساب «فایربیس» (Firebase) داشته باشید. اگر چنین حسابی ندارید به این صفحه (+) مراجعه کنید و یک حساب باز کنید. توجه داشته باشید در زمان نگارش مقاله، این حساب برای دسترسی ایرانیان مسدود بوده است و برای دسترسی به آن نیاز به استفاده از پراکسی وجود دارد.

ایجاد یک پروژه روی فایربیس

زمانی که یک حساب کاربری روی فایربیس باز کردید، به این صفحه (+) بروید و روی add project کلیک کنید.

یک نام به پروژه خود بدهید و روی Create کلیک کنید. ممکن است چند ثانیه طول بکشد تا پروژه شما آماده شود. سپس در ادامه یک اپلیکیشن اندروید به پروژه خود اضافه می‌کنیم.

افزودن اپلیکیشن

اندروید استودیو را باز کنید و یک پروژه جدید با یک اکتیویتی خالی اضافه کنید. سپس روی Tools -> Firebase کلیک کنید. بدین ترتیب دستیار فایربیس در پنل سمت راست باز می‌شود. در فهرست گزینه‌ها، ML Kit را انتخاب کرده و روی گزینه زیر کلیک کنید:

Use ML Kit to detect faces in images and video

احتمالاً از شما درخواست می‌شود که اندروید استودیو خود را به یک اپلیکیشن در فایربیس وصل کنید. روی connect کلیک کرده و در پروژه فایربیس خود sign in کنید. زمانی که اندروید استودیو اجازه دسترسی به پروژه فایربیس را داد، از شما خواسته می‌شود که یک پروژه انتخاب کنید. پروژه‌ای را که در گام قبلی ایجاد کردید انتخاب کنید. پس از آن باید ML Kit را به اپلیکیشن خود اضافه کنید که یک فرایند تک کلیکی محسوب می‌شود. زمانی که کار اضافه کردن وابستگی‌ها به پایان رسید، آماده هستید که اپلیکیشن خود را ایجاد کنید.

پیکربندی AndroidManifest.xml

شما باید فایل AndroidManifest.xml خود را طوری ویرایش کنید که امکان یادگیری ماشین آفلاین در اپلیکیشن اندروید خود را داشته باشید. متا-تگ زیر را درست زیر تگ اپلیکیشن خود وارد کنید.

1
2
3
<meta-data
        android:name="com.google.firebase.ml.vision.DEPENDENCIES"
        android:value="face"/>

ضمناً قصد داریم یک قابلیت دوربین به اپلیکیشن خود اضافه کنیم و از این رو یک تگ permission در مانیفست اضافه می‌کنیم.

1
<uses-permission android:name="android.permission.CAMERA"/>

افزودن یک دوربین به اپلیکیشن

برای افزودن دوربین به اپلیکیشن باید CameraKit مربوط به WonderKiln را اضافه کنیم. برای استفاده از CameraKit وابستگی‌های زیر را در فایل build.gradle سطح اپلیکیشن اضافه می‌کنیم.

1
2
3
4
implementation 'com.camerakit:camerakit:1.0.0-beta3.11'
implementation 'com.camerakit:jpegkit:0.1.0'
implementation 'org.jetbrains.kotlin:kotlin-stdlib-jdk7:1.3.31'
implementation 'org.jetbrains.kotlinx:kotlinx-coroutines-android:1.0.0'

نکته: اگر می‌خواهید از کاتلین در اپلیکیشن اندروید خود استفاده کنید، باید وابستگی‌های کاتلین نیز در آن گنجانده شوند.

پروژه را Sync کنید تا وابستگی‌ها دانلود شوند. سپس یک CameraKitView در فایل لی‌آوت activity_main.xml اضافه می‌کنیم. به این منظور کد زیر را در فایل لی‌‌آوت اضافه کنید.

1
2
3
4
5
6
7
8
9
10
11
12
<com.camerakit.CameraKitView
        android:layout_above="@id/btn_detect"
        android:layout_width="match_parent"
        android:id="@+id/camera_view"
        android:layout_height="match_parent"
        android:adjustViewBounds="true"
        android:keepScreenOn="true"
        app:camera_flash="auto"
        app:camera_facing="back"
        app:camera_focus="continuous"
        app:camera_permissions="camera">
</com.camerakit.CameraKitView>

همچنین یک دکمه به زیر صفحه اضافه می‌کنیم تا به وسیله آن عکس بگیریم.

1
2
3
4
5
<Button android:layout_width="match_parent" android:layout_height="wrap_content"
        android:layout_alignParentBottom="true"
        android:layout_centerHorizontal="true"
        android:id="@+id/btn_detect"
        android:text="Detect"/>

پیکربندی دوربین

ما دوربین را در فایل MainActivity.kt مقداردهی می‌کنیم. به این منظور برخی متدهای چرخه عمر را override خواهیم کرد و درون این متدها، متدهای چرخه عمر را برای دوربین فراخوانی می‌کنیم:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
override fun onResume() {
    super.onResume()
    camera_view.onResume()
}
override fun onPause() {
    super.onPause()
    camera_view.onPause()
}
override fun onStart() {
    super.onStart()
    camera_view.onStart()
}
override fun onStop() {
    super.onStop()
    camera_view.onStop()
}

از اندروید نسخه M به بعد باید مجوزهای زمان اجرا را نیز تقاضا کنیم. این وضعیت از سوی خود کتابخانه CameraKit مربوط به WonderKiln مدیریت می‌شود. به این منظور کافی است متد زیر را override کنیم:

1
2
3
4
override fun onRequestPermissionsResult(requestCode: Int, permissions: Array<String>, grantResults: IntArray) {
    super.onRequestPermissionsResult(requestCode, permissions, grantResults)
    camera_view.onRequestPermissionsResult(requestCode, permissions, grantResults)
}

عکس گرفتن

ما با فشردن دکمه یک عکس می‌گیریم و آن را به دتکتور ارسال می‌کنیم. سپس یک مدل یادگیری ماشین روی تصویر اعمال می‌کنیم تا چهره را شناسایی کنیم. یک onclicklistener روی دکمه و درون تابع onClick تنظیم می‌کنیم و درون آن تابع captureImage مربوط به ویوی Camera را فراخوانی می‌کنیم.

1
2
3
4
btn_detect.setOnClickListener {
            camera_view.captureImage { cameraKitView, byteArray ->
            }
        }

در ادامه مقدار byteArray دریافتی را در یک bitmap دیکود می‌کنیم و سپس bitmap را به یک اندازه معقول مقیاس‌بندی می‌نماییم. این اندازه اساساً باید به اندازه camera_view ما باشد.

1
2
3
4
5
6
7
8
9
10
btn_detect.setOnClickListener {
            camera_view.captureImage { cameraKitView, byteArray ->
                camera_view.onStop()
                alertDialog.show()
                var bitmap = BitmapFactory.decodeByteArray(byteArray, 0, byteArray?.size ?: 0)
                bitmap = Bitmap.createScaledBitmap(bitmap, camera_view?.width ?: 0, camera_view?.height ?: 0, false)
                runDetector(bitmap)
            }
            graphic_overlay.clear()
        }

اکنون زمان آن فرا رسیده است که دتکتور ما روی bitmap اجرا شود. به این منظور تابع جداگانه runDetector() اجرا می‌کنیم.

شروع تشخیص

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

1
val image = FirebaseVisionImage.fromBitmap(bitmap)

سپس نوبت آن می‌رسد که برخی گزینه‌ها مانند performanceMode ،countourMode ،landmarkMode و غیره را اضافه کنیم.

1
2
3
val options = FirebaseVisionFaceDetectorOptions.Builder()
 
.build()

اکنون دتکتور خود را با استفاده از گزینه‌ها می‌سازیم.

1
2
val detector = FirebaseVision.getInstance()
    .getVisionFaceDetector(options)

در نهایت، نوبت آن می‌رسد که فرایند شناسایی را شروع کنیم. ما با استفاده از این دتکتور تابع detectInImage را فراخوانی کرده و تصویر را به آن ارسال می‌کنیم. در ادامه callback-هایی برای موفقیت یا شکست دریافت می‌کنیم.

طرز کار تابع runDetector به صورت زیر است:

1
2
3
4
5
6
7
8
9
10
11
12
13
private fun runDetector(bitmap: Bitmap) {
    val image = FirebaseVisionImage.fromBitmap(bitmap)
    val options = FirebaseVisionFaceDetectorOptions.Builder()
        .build()
    val detector = FirebaseVision.getInstance()
        .getVisionFaceDetector(options)
    detector.detectInImage(image)
        .addOnSuccessListener { faces ->
            processFaceResult(faces)
        }.addOnFailureListener {
            it.printStackTrace()
        }
}

ایجاد کادر پیرامونی

برای ایجاد یک کادر پیرامونی که چهره‌های شناسایی‌شده را احاطه کند، باید دو view ایجاد کنیم. ویوی اول یک ویوی رویی شفاف است که روی آن کادر را رسم می‌کنیم. سپس کادر واقعی را روی تصویر قرار می‌دهیم.

فایل GraphicOverlay.java به صورت زیر است:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
public class GraphicOverlay extends View {
    private final Object mLock = new Object();
    private int mPreviewWidth;
    private float mWidthScaleFactor = 1.0f;
    private int mPreviewHeight;
    private float mHeightScaleFactor = 1.0f;
    private int mFacing = CameraSource.CAMERA_FACING_BACK;
    private Set<Graphic> mGraphics = new HashSet<>();
    /**
     * Base class for a custom graphics object to be rendered within the graphic overlay.  Subclass
     * this and implement the {@link Graphic#draw(Canvas)} method to define the
     * graphics element.  Add instances to the overlay using {@link GraphicOverlay#add(Graphic)}.
     */
    public static abstract class Graphic {
        private GraphicOverlay mOverlay;
        public Graphic(GraphicOverlay overlay) {
            mOverlay = overlay;
        }
        /**
         * Draw the graphic on the supplied canvas.  Drawing should use the following methods to
         * convert to view coordinates for the graphics that are drawn:
         * <ol>
         * <li>{@link Graphic#scaleX(float)} and {@link Graphic#scaleY(float)} adjust the size of
         * the supplied value from the preview scale to the view scale.</li>
         * <li>{@link Graphic#translateX(float)} and {@link Graphic#translateY(float)} adjust the
         * coordinate from the preview's coordinate system to the view coordinate system.</li>
         * </ol>
         *
         * @param canvas drawing canvas
         */
        public abstract void draw(Canvas canvas);
        /**
         * Adjusts a horizontal value of the supplied value from the preview scale to the view
         * scale.
         */
        public float scaleX(float horizontal) {
            return horizontal * mOverlay.mWidthScaleFactor;
        }
        /**
         * Adjusts a vertical value of the supplied value from the preview scale to the view scale.
         */
        public float scaleY(float vertical) {
            return vertical * mOverlay.mHeightScaleFactor;
        }
        /**
         * Adjusts the x coordinate from the preview's coordinate system to the view coordinate
         * system.
         */
        public float translateX(float x) {
            if (mOverlay.mFacing == CameraSource.CAMERA_FACING_FRONT) {
                return mOverlay.getWidth() - scaleX(x);
            } else {
                return scaleX(x);
            }
        }
        /**
         * Adjusts the y coordinate from the preview's coordinate system to the view coordinate
         * system.
         */
        public float translateY(float y) {
            return scaleY(y);
        }
        public void postInvalidate() {
            mOverlay.postInvalidate();
        }
    }
    public GraphicOverlay(Context context, AttributeSet attrs) {
        super(context, attrs);
    }
    /**
     * Removes all graphics from the overlay.
     */
    public void clear() {
        synchronized (mLock) {
            mGraphics.clear();
        }
        postInvalidate();
    }
    /**
     * Adds a graphic to the overlay.
     */
    public void add(Graphic graphic) {
        synchronized (mLock) {
            mGraphics.add(graphic);
        }
        postInvalidate();
    }
    /**
     * Removes a graphic from the overlay.
     */
    public void remove(Graphic graphic) {
        synchronized (mLock) {
            mGraphics.remove(graphic);
        }
        postInvalidate();
    }
    /**
     * Sets the camera attributes for size and facing direction, which informs how to transform
     * image coordinates later.
     */
    public void setCameraInfo(int previewWidth, int previewHeight, int facing) {
        synchronized (mLock) {
            mPreviewWidth = previewWidth;
            mPreviewHeight = previewHeight;
            mFacing = facing;
        }
        postInvalidate();
    }
    /**
     * Draws the overlay with its associated graphic objects.
     */
    @Override
    protected void onDraw(Canvas canvas) {
        super.onDraw(canvas);
        synchronized (mLock) {
            if ((mPreviewWidth != 0) && (mPreviewHeight != 0)) {
                mWidthScaleFactor = (float) canvas.getWidth() / (float) mPreviewWidth;
                mHeightScaleFactor = (float) canvas.getHeight() / (float) mPreviewHeight;
            }
            for (Graphic graphic : mGraphics) {
                graphic.draw(canvas);
            }
        }
    }
}

کادر مستطیلی واقعی به صورت زیر است:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class RectOverlay extends GraphicOverlay.Graphic {
    private int RECT_COLOR = Color.RED;
    private float strokeWidth = 4.0f;
    private Paint rectPaint;
    private Rect rect;
    private GraphicOverlay graphicOverlay;
    public RectOverlay(GraphicOverlay graphicOverlay, Rect rect) {
        super(graphicOverlay);
        this.graphicOverlay = graphicOverlay;
        this.rect = rect;
        rectPaint = new Paint();
        rectPaint.setColor(RECT_COLOR);
        rectPaint.setStyle(Paint.Style.STROKE);
        rectPaint.setStrokeWidth(strokeWidth);
        postInvalidate();
    }
 
 
    @Override
    public void draw(Canvas canvas) {
        RectF rectF = new RectF(rect);
        rectF.left = translateX(rectF.left);
        rectF.right = translateX(rectF.right);
        rectF.top = translateY(rectF.top);
        rectF.bottom = translateY(rectF.bottom);
        canvas.drawRect(rectF, rectPaint);
    }
}

اینک زمان آن رسیده که این ویوی graphicOverlay را در فایل لی‌آوت activity_main.xml خود اضافه کنیم.

1
2
3
<com.example.imagelove.GraphicOverlay
        android:id="@+id/graphic_overlay"
        android:layout_width="match_parent" android:layout_height="match_parent"/>

در نهایت فایل activity_main.xml به صورت زیر درمی‌آید:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
<?xml version="1.0" encoding="utf-8"?>
<RelativeLayout
        xmlns:android="http://schemas.android.com/apk/res/android"
        xmlns:tools="http://schemas.android.com/tools"
        xmlns:app="http://schemas.android.com/apk/res-auto"
        android:layout_width="match_parent" android:layout_height="match_parent"
        tools:context=".MainActivity">
    <Button android:layout_width="match_parent" android:layout_height="wrap_content"
            android:layout_alignParentBottom="true"
            android:layout_centerHorizontal="true"
            android:id="@+id/btn_detect"
            android:text="Detect"/>
    <com.camerakit.CameraKitView
            android:layout_above="@id/btn_detect"
            android:layout_width="match_parent"
            android:id="@+id/camera_view"
            android:layout_height="match_parent"
            android:adjustViewBounds="true"
            android:keepScreenOn="true"
            app:camera_flash="auto"
            app:camera_facing="back"
            app:camera_focus="continuous"
            app:camera_permissions="camera">
    </com.camerakit.CameraKitView>
    <com.example.imagelove.GraphicOverlay
            android:id="@+id/graphic_overlay"
            android:layout_width="match_parent" android:layout_height="match_parent"/>
</RelativeLayout>

اینک زمان آن است که کادر پیرامونی چهره‌های شناسایی‌ شده را رسم کنیم. ما با استفاده از دتکتور چهره‌ها را در تابع ()processFaceResult دریافت کرده‌ایم.

در ادامه حلقه‌ای روی همه چهره‌ها تعریف کرده و یک کادر روی هر چهره به صورت زیر اضافه می‌کنیم:

1
2
3
4
5
6
7
8
private fun processFaceResult(faces: MutableList<FirebaseVisionFace>) {
    faces.forEach {
        val bounds = it.boundingBox
        val rectOverLay = RectOverlay(graphic_overlay, bounds)
        graphic_overlay.add(rectOverLay)
    }
    alertDialog.dismiss()
}

سخن پایانی

در نهایت اپلیکیشن ما چیزی مانند تصویر زیر خواهد بود:

شما می‌توانید سورس کد این اپلیکیشن را از این صفحه گیت‌هاب (+) دانلود کنید. روی این کد کار کنید و ایده‌های مختلفی که برای پیاده‌سازی یادگیری ماشین در اپلیکیشن‌های اندرویدی دارید امتحان نمایید.

منبع: فرادرس

مشاوره جمعه 14 تیر 1398 ساعت 18:17

0 نظر

آموزش Node.js: کار با فایل توسط ماژول fs — بخش نهم

مشاوره جمعه 14 تیر 1398 ساعت 18:14

0 نظر

برنامه بررسی وجود دور در گراف بدون جهت — راهنمای کاربردی

در این مطلب، برنامه بررسی وجود دور در گراف بدون جهت در زبان‌های برنامه‌نویسی «سی‌پلاس‌پلاس» (++C)، «پایتون» (Python) و«جاوا» (Java) ارائه شده است. در ادامه، مساله تعریف و همراه با مثالی حل می‌شود. یک گراف بدون جهت داده شده است. هدف آن است که بررسی شود آیا دوری در گراف وجود دارد یا نه. برای مثال، گراف زیر دارای دور 1-2-۰-1 است.

برنامه بررسی وجود دور در گراف بدون جهت

پیش از این، در مطلبی با عنوان «برنامه تشخیص وجود دور در گراف جهت دار — راهنمای کاربردی»، روش پیدا کردن دور در گراف جهت دار مورد بررسی قرار گرفت. پیچیدگی زمانی الگوریتم مجموعه‌های مجزا برابر با (O(ELogV است. می‌توان همچون گراف جهت‌دار، از «جستجوی اول عمق» (Depth First Search | DFS) برای شناسایی دور در گراف‌های بدون جهت در زمان (O(V+E استفاده کرد. پیمایش گراف داده شده با استفاده از DFS انجام می‌شود. برای هر راس بازدید شده V، اگر راس همسایه u وجود دارد که پیش از این بازدید شده باشد و u والد v نباشد، دور در گراف وجود دارد. اگر چنین راس مجاوری برای هیچ راسی یافت نشود، گفته می‌شود که گراف فاقد دور است. فرض این رویکرد آن است که هیچ دو یال موازی بین دو راس وجود نداشته باشد.

برنامه بررسی وجود دور در گراف بدون جهت در ++C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
// A C++ Program to detect cycle in an undirected graph 
#include<iostream> 
#include <list> 
#include <limits.h> 
using namespace std; 
  
// Class for an undirected graph 
class Graph 
{ 
    int V;    // No. of vertices 
    list<int> *adj;    // Pointer to an array containing adjacency lists 
    bool isCyclicUtil(int v, bool visited[], int parent); 
public: 
    Graph(int V);   // Constructor 
    void addEdge(int v, int w);   // to add an edge to graph 
    bool isCyclic();   // returns true if there is a cycle 
}; 
  
Graph::Graph(int V) 
{ 
    this->V = V; 
    adj = new list<int>[V]; 
} 
  
void Graph::addEdge(int v, int w) 
{ 
    adj[v].push_back(w); // Add w to v’s list. 
    adj[w].push_back(v); // Add v to w’s list. 
} 
  
// A recursive function that uses visited[] and parent to detect 
// cycle in subgraph reachable from vertex v. 
bool Graph::isCyclicUtil(int v, bool visited[], int parent) 
{ 
    // Mark the current node as visited 
    visited[v] = true; 
  
    // Recur for all the vertices adjacent to this vertex 
    list<int>::iterator i; 
    for (i = adj[v].begin(); i != adj[v].end(); ++i) 
    { 
        // If an adjacent is not visited, then recur for that adjacent 
        if (!visited[*i]) 
        { 
           if (isCyclicUtil(*i, visited, v)) 
              return true; 
        } 
  
        // If an adjacent is visited and not parent of current vertex, 
        // then there is a cycle. 
        else if (*i != parent) 
           return true; 
    } 
    return false; 
} 
  
// Returns true if the graph contains a cycle, else false. 
bool Graph::isCyclic() 
{ 
    // Mark all the vertices as not visited and not part of recursion 
    // stack 
    bool *visited = new bool[V]; 
    for (int i = 0; i < V; i++) 
        visited[i] = false; 
  
    // Call the recursive helper function to detect cycle in different 
    // DFS trees 
    for (int u = 0; u < V; u++) 
        if (!visited[u]) // Don't recur for u if it is already visited 
          if (isCyclicUtil(u, visited, -1)) 
             return true; 
  
    return false; 
} 
  
// Driver program to test above functions 
int main() 
{ 
    Graph g1(5); 
    g1.addEdge(1, 0); 
    g1.addEdge(0, 2); 
    g1.addEdge(2, 0); 
    g1.addEdge(0, 3); 
    g1.addEdge(3, 4); 
    g1.isCyclic()? cout << "Graph contains cycle\n": 
                   cout << "Graph doesn't contain cycle\n"; 
  
    Graph g2(3); 
    g2.addEdge(0, 1); 
    g2.addEdge(1, 2); 
    g2.isCyclic()? cout << "Graph contains cycle\n": 
                   cout << "Graph doesn't contain cycle\n"; 
  
    return 0; 
}

برنامه بررسی وجود دور در گراف بدون جهت در جاوا

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// A Java Program to detect cycle in an undirected graph 
import java.io.*; 
import java.util.*; 
  
// This class represents a directed graph using adjacency list 
// representation 
class Graph 
{ 
    private int V;   // No. of vertices 
    private LinkedList<Integer> adj[]; // Adjacency List Represntation 
  
    // Constructor 
    Graph(int v) { 
        V = v; 
        adj = new LinkedList[v]; 
        for(int i=0; i<v; ++i) 
            adj[i] = new LinkedList(); 
    } 
  
    // Function to add an edge into the graph 
    void addEdge(int v,int w) { 
        adj[v].add(w); 
        adj[w].add(v); 
    } 
  
    // A recursive function that uses visited[] and parent to detect 
    // cycle in subgraph reachable from vertex v. 
    Boolean isCyclicUtil(int v, Boolean visited[], int parent) 
    { 
        // Mark the current node as visited 
        visited[v] = true; 
        Integer i; 
  
        // Recur for all the vertices adjacent to this vertex 
        Iterator<Integer> it = adj[v].iterator(); 
        while (it.hasNext()) 
        { 
            i = it.next(); 
  
            // If an adjacent is not visited, then recur for that 
            // adjacent 
            if (!visited[i]) 
            { 
                if (isCyclicUtil(i, visited, v)) 
                    return true; 
            } 
  
            // If an adjacent is visited and not parent of current 
            // vertex, then there is a cycle. 
            else if (i != parent) 
                return true; 
        } 
        return false; 
    } 
  
    // Returns true if the graph contains a cycle, else false. 
    Boolean isCyclic() 
    { 
        // Mark all the vertices as not visited and not part of 
        // recursion stack 
        Boolean visited[] = new Boolean[V]; 
        for (int i = 0; i < V; i++) 
            visited[i] = false; 
  
        // Call the recursive helper function to detect cycle in 
        // different DFS trees 
        for (int u = 0; u < V; u++) 
            if (!visited[u]) // Don't recur for u if already visited 
                if (isCyclicUtil(u, visited, -1)) 
                    return true; 
  
        return false; 
    } 
  
  
    // Driver method to test above methods 
    public static void main(String args[]) 
    { 
        // Create a graph given in the above diagram 
        Graph g1 = new Graph(5); 
        g1.addEdge(1, 0); 
        g1.addEdge(0, 2); 
        g1.addEdge(2, 0); 
        g1.addEdge(0, 3); 
        g1.addEdge(3, 4); 
        if (g1.isCyclic()) 
            System.out.println("Graph contains cycle"); 
        else
            System.out.println("Graph doesn't contains cycle"); 
  
        Graph g2 = new Graph(3); 
        g2.addEdge(0, 1); 
        g2.addEdge(1, 2); 
        if (g2.isCyclic()) 
            System.out.println("Graph contains cycle"); 
        else
            System.out.println("Graph doesn't contains cycle"); 
    } 
} 
// This code is contributed by Aakash Hasija

برنامه بررسی وجود دور در گراف بدون جهت در پایتون

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
# Python Program to detect cycle in an undirected graph 
  
from collections import defaultdict 
   
#This class represents a undirected graph using adjacency list representation 
class Graph: 
   
    def __init__(self,vertices): 
        self.V= vertices #No. of vertices 
        self.graph = defaultdict(list) # default dictionary to store graph 
  
   
    # function to add an edge to graph 
    def addEdge(self,v,w): 
        self.graph[v].append(w) #Add w to v_s list 
        self.graph[w].append(v) #Add v to w_s list 
   
    # A recursive function that uses visited[] and parent to detect 
    # cycle in subgraph reachable from vertex v. 
    def isCyclicUtil(self,v,visited,parent): 
  
        #Mark the current node as visited  
        visited[v]= True
  
        #Recur for all the vertices adjacent to this vertex 
        for i in self.graph[v]: 
            # If the node is not visited then recurse on it 
            if  visited[i]==False :  
                if(self.isCyclicUtil(i,visited,v)): 
                    return True
            # If an adjacent vertex is visited and not parent of current vertex, 
            # then there is a cycle 
            elif  parent!=i: 
                return True
          
        return False
           
   
    #Returns true if the graph contains a cycle, else false. 
    def isCyclic(self): 
        # Mark all the vertices as not visited 
        visited =[False]*(self.V) 
        # Call the recursive helper function to detect cycle in different 
        #DFS trees 
        for i in range(self.V): 
            if visited[i] ==False: #Don't recur for u if it is already visited 
                if(self.isCyclicUtil(i,visited,-1))== True: 
                    return True
          
        return False
  
# Create a graph given in the above diagram 
g = Graph(5) 
g.addEdge(1, 0) 
g.addEdge(0, 2) 
g.addEdge(2, 0) 
g.addEdge(0, 3) 
g.addEdge(3, 4) 
  
if g.isCyclic(): 
    print "Graph contains cycle"
else : 
    print "Graph does not contain cycle "
g1 = Graph(3) 
g1.addEdge(0,1) 
g1.addEdge(1,2) 
  
  
if g1.isCyclic(): 
    print "Graph contains cycle"
else : 
    print "Graph does not contain cycle "
   
#This code is contributed by Neelam Yadav

خروجی

Graph contains cycle
Graph doesn't contain cycle

پیچیدگی زمانی

برنامه، یک پیمایش ساده DFS را در گراف انجام می‌دهد و گراف با استفاده از لیست هم‌جواری نشان داده می‌شود. بنابراین، پیچیدگی زمانی از درجه (O(V+E است.

منبع: فرادرس

مشاوره جمعه 14 تیر 1398 ساعت 18:13

0 نظر

جستجوی دودویی — به زبان ساده

در این مطلب، الگوریتم جستجوی دودویی (Binary Search) مورد بررسی قرار گرفته و پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون انجام شده است.

جستجوی دودویی

در جستجوی دودویی (Binary Search)‌، جستجو در یک آرایه مرتب شده، با تقسیم تکرار شونده بازه جستجو به نصف، انجام می‌شود. کار با بازه‌ای که کل آرایه را پوشش می‌دهد، آغاز می‌شود. اگر مقدار کلید جستجو برابر با عنصر میانی باشد، اندیس آن بازگردانده می‌شود. در غیر این صورت، اگر مقدار کلید جستجو کمتر از عنصری باشد که در میانه بازه قرار دارد، بازه شکسته شده و جستجو در نیمه کمتر ادامه پیدا می‌کند. در صورتی که مقدار کلید جستجو بزرگ‌تر از اندیس میانی آرایه باشد، جستجو در نیمه بیشتر (حاوی مقادیر بزرگ‌تر) آرایه ادامه پیدا می‌کند. کار شکستن آرایه به دو نیم و انتخاب نیمه‌ای که جستجو باید در آن انجام شود، مکررا و تا هنگامی که عنصر مورد نظر در آرایه یافته شود و یا مشخص شود که عنصر مورد نظر در آرایه وجود ندارد، ادامه خواهد داشت.

مثالی از جستجوی دودویی

آرایه مرتب شده []arr شامل n عنصر موجود است. هدف، نوشتن تابعی است که یک عنصر داده شده x را در آرایه مذکور ([]arr) جستجو کند. یک رویکرد ساده برای انجام این کار، استفاده از «جستجوی خطی» (Linear Search) است. پیچیدگی زمانی الگوریتم جستجوی خطی، (O(n است. رویکرد دیگر، انجام کار مشابهی با استفاده از «جستجوی دودویی» (Binary Search) است. ایده اصلی نهفته در پس جستجوی دودویی، استفاده از اطلاعات موجود در آرایه مرتب شده و کاهش پیچیدگی زمانی به (O(Log n است. در جستجوی دودویی اساسا نیمی از عناصر تنها پس از یک مقایسه حذف می‌شوند. برای انجام جستجو، از الگوریتم زیر استفاده می‌شود.

x با عنصر میانی آرایه مقایسه می‌شود.
اگر x با عنصر میانی آرایه یکی بود، اندیس عنصر میانی را بازگردان.
در غیر این صورت، اگر x بزرگ‌تر از عنصر میانی بود، امکان دارد x در نیمه سمت راست آرایه، پس از عنصر میانی، قرار داشته باشد (شایان توجه است که همانطور که پیش‌تر اشاره شد، آرایه مرتب شده است. پس در این حالت، نیمه‌ای با مقادیر بزرگ‌تر برای ادامه جستجو گزینش می‌شود).
در غیر این صورت، اگر x از عنصر میانی آرایه کوچک‌تر باشد، آرایه به دو نیمه شکسته شده و جستجو در نیمه سمت چپ (با مقادیر کوچک‌تر از میانه)، ادامه پیدا می‌کند.

در ادامه، پیاده‌سازی الگوریتم جستجوی دودویی به صورت بازگشتی، در زبان‌های برنامه‌نویسی C++ ،C، «جاوا» (Java)، «پایتون» (Python)، «سی‌شارپ» (#C) و PHP ارائه شده است.

کد بازگشتی الگوریتم جستجوی دودویی در C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// C program to implement recursive Binary Search 
#include <stdio.h> 
  
// A recursive binary search function. It returns 
// location of x in given array arr[l..r] is present, 
// otherwise -1 
int binarySearch(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 
  
        // If the element is present at the middle 
        // itself 
        if (arr[mid] == x) 
            return mid; 
  
        // If element is smaller than mid, then 
        // it can only be present in left subarray 
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 
  
        // Else the element can only be present 
        // in right subarray 
        return binarySearch(arr, mid + 1, r, x); 
    } 
  
    // We reach here when element is not 
    // present in array 
    return -1; 
} 
  
int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int x = 10; 
    int result = binarySearch(arr, 0, n - 1, x); 
    (result == -1) ? printf("Element is not present in array") 
                   : printf("Element is present at index %d", 
                            result); 
    return 0; 
}

کد بازگشتی الگوریتم جستجوی دودویی در ++C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// C++ program to implement recursive Binary Search 
#include <iostream> 
using namespace std; 
  
// A recursive binary search function. It returns 
// location of x in given array arr[l..r] is present, 
// otherwise -1 
int binarySearch(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 
  
        // If the element is present at the middle 
        // itself 
        if (arr[mid] == x) 
            return mid; 
  
        // If element is smaller than mid, then 
        // it can only be present in left subarray 
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 
  
        // Else the element can only be present 
        // in right subarray 
        return binarySearch(arr, mid + 1, r, x); 
    } 
  
    // We reach here when element is not 
    // present in array 
    return -1; 
} 
  
int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int x = 10; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int result = binarySearch(arr, 0, n - 1, x); 
    (result == -1) ? cout << "Element is not present in array"
                   : cout << "Element is present at index " << result; 
    return 0; 
}

کد بازگشتی الگوریتم جستجوی دودویی در جاوا

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// Java implementation of recursive Binary Search 
class BinarySearch { 
    // Returns index of x if it is present in arr[l.. 
    // r], else return -1 
    int binarySearch(int arr[], int l, int r, int x) 
    { 
        if (r >= l) { 
            int mid = l + (r - l) / 2; 
  
            // If the element is present at the 
            // middle itself 
            if (arr[mid] == x) 
                return mid; 
  
            // If element is smaller than mid, then 
            // it can only be present in left subarray 
            if (arr[mid] > x) 
                return binarySearch(arr, l, mid - 1, x); 
  
            // Else the element can only be present 
            // in right subarray 
            return binarySearch(arr, mid + 1, r, x); 
        } 
  
        // We reach here when element is not present 
        // in array 
        return -1; 
    } 
  
    // Driver method to test above 
    public static void main(String args[]) 
    { 
        BinarySearch ob = new BinarySearch(); 
        int arr[] = { 2, 3, 4, 10, 40 }; 
        int n = arr.length; 
        int x = 10; 
        int result = ob.binarySearch(arr, 0, n - 1, x); 
        if (result == -1) 
            System.out.println("Element not present"); 
        else
            System.out.println("Element found at index " + result); 
    } 
} 
/* This code is contributed by Rajat Mishra */

کد بازگشتی الگوریتم جستجوی دودویی در پایتون

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# Python Program for recursive binary search. 
  
# Returns index of x in arr if present, else -1 
def binarySearch (arr, l, r, x): 
  
    # Check base case 
    if r >= l: 
  
        mid = l + (r - l)/2
  
        # If element is present at the middle itself 
        if arr[mid] == x: 
            return mid 
          
        # If element is smaller than mid, then it  
        # can only be present in left subarray 
        elif arr[mid] > x: 
            return binarySearch(arr, l, mid-1, x) 
  
        # Else the element can only be present  
        # in right subarray 
        else: 
            return binarySearch(arr, mid + 1, r, x) 
  
    else: 
        # Element is not present in the array 
        return -1
  
# Test array 
arr = [ 2, 3, 4, 10, 40 ] 
x = 10
  
# Function call 
result = binarySearch(arr, 0, len(arr)-1, x) 
  
if result != -1: 
    print "Element is present at index % d" % result 
else: 
    print "Element is not present in array"

کد بازگشتی الگوریتم جستجوی دودویی در #C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// C# implementation of recursive Binary Search 
using System; 
  
class GFG { 
    // Returns index of x if it is present in 
    // arr[l..r], else return -1 
    static int binarySearch(int[] arr, int l, 
                            int r, int x) 
    { 
        if (r >= l) { 
            int mid = l + (r - l) / 2; 
  
            // If the element is present at the 
            // middle itself 
            if (arr[mid] == x) 
                return mid; 
  
            // If element is smaller than mid, then 
            // it can only be present in left subarray 
            if (arr[mid] > x) 
                return binarySearch(arr, l, mid - 1, x); 
  
            // Else the element can only be present 
            // in right subarray 
            return binarySearch(arr, mid + 1, r, x); 
        } 
  
        // We reach here when element is not present 
        // in array 
        return -1; 
    } 
  
    // Driver method to test above 
    public static void Main() 
    { 
  
        int[] arr = { 2, 3, 4, 10, 40 }; 
        int n = arr.Length; 
        int x = 10; 
  
        int result = binarySearch(arr, 0, n - 1, x); 
  
        if (result == -1) 
            Console.WriteLine("Element not present"); 
        else
            Console.WriteLine("Element found at index "
                              + result); 
    } 
} 
  
// This code is contributed by Sam007.

کد بازگشتی الگوریتم جستجوی دودویی در PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
<?php 
// PHP program to implement 
// recursive Binary Search 
  
// A recursive binary search 
// function. It returns location 
// of x in given array arr[l..r]  
// is present, otherwise -1 
function binarySearch($arr, $l, $r, $x) 
{ 
if ($r >= $l) 
{ 
        $mid = ceil($l + ($r - $l) / 2); 
  
        // If the element is present  
        // at the middle itself 
        if ($arr[$mid] == $x)  
            return floor($mid); 
  
        // If element is smaller than  
        // mid, then it can only be  
        // present in left subarray 
        if ($arr[$mid] > $x)  
            return binarySearch($arr, $l,  
                                $mid - 1, $x); 
  
        // Else the element can only  
        // be present in right subarray 
        return binarySearch($arr, $mid + 1,  
                            $r, $x); 
} 
  
// We reach here when element  
// is not present in array 
return -1; 
} 
  
// Driver Code 
$arr = array(2, 3, 4, 10, 40); 
$n = count($arr); 
$x = 10; 
$result = binarySearch($arr, 0, $n - 1, $x); 
if(($result == -1)) 
echo "Element is not present in array"; 
else
echo "Element is present at index ", 
                            $result; 
                              
// This code is contributed by anuj_67. 
?>

خروجی

Element is present at index 3

در ادامه، کد مربوط به پیاده‌سازی الگوریتم جستجوی دودویی به صورت «تکرار شونده» (Iterative) ارائه شده است.

کد تکرار شونده الگوریتم جستجوی دودویی در C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// C program to implement iterative Binary Search 
#include <stdio.h> 
  
// A iterative binary search function. It returns 
// location of x in given array arr[l..r] if present, 
// otherwise -1 
int binarySearch(int arr[], int l, int r, int x) 
{ 
    while (l <= r) { 
        int m = l + (r - l) / 2; 
  
        // Check if x is present at mid 
        if (arr[m] == x) 
            return m; 
  
        // If x greater, ignore left half 
        if (arr[m] < x) 
            l = m + 1; 
  
        // If x is smaller, ignore right half 
        else
            r = m - 1; 
    } 
  
    // if we reach here, then element was 
    // not present 
    return -1; 
} 
  
int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int x = 10; 
    int result = binarySearch(arr, 0, n - 1, x); 
    (result == -1) ? printf("Element is not present"
                            " in array") 
                   : printf("Element is present at "
                            "index %d", 
                            result); 
    return 0; 
}

کد تکرار شونده الگوریتم جستجوی دودویی در ++C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// C++ program to implement recursive Binary Search 
#include <iostream> 
using namespace std; 
  
// A iterative binary search function. It returns 
// location of x in given array arr[l..r] if present, 
// otherwise -1 
int binarySearch(int arr[], int l, int r, int x) 
{ 
    while (l <= r) { 
        int m = l + (r - l) / 2; 
  
        // Check if x is present at mid 
        if (arr[m] == x) 
            return m; 
  
        // If x greater, ignore left half 
        if (arr[m] < x) 
            l = m + 1; 
  
        // If x is smaller, ignore right half 
        else
            r = m - 1; 
    } 
  
    // if we reach here, then element was 
    // not present 
    return -1; 
} 
  
int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int x = 10; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int result = binarySearch(arr, 0, n - 1, x); 
    (result == -1) ? cout << "Element is not present in array"
                   : cout << "Element is present at index " << result; 
    return 0; 
}

کد تکرار شونده الگوریتم جستجوی دودویی در جاوا

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// Java implementation of iterative Binary Search 
class BinarySearch { 
    // Returns index of x if it is present in arr[], 
    // else return -1 
    int binarySearch(int arr[], int x) 
    { 
        int l = 0, r = arr.length - 1; 
        while (l <= r) { 
            int m = l + (r - l) / 2; 
  
            // Check if x is present at mid 
            if (arr[m] == x) 
                return m; 
  
            // If x greater, ignore left half 
            if (arr[m] < x) 
                l = m + 1; 
  
            // If x is smaller, ignore right half 
            else
                r = m - 1; 
        } 
  
        // if we reach here, then element was 
        // not present 
        return -1; 
    } 
  
    // Driver method to test above 
    public static void main(String args[]) 
    { 
        BinarySearch ob = new BinarySearch(); 
        int arr[] = { 2, 3, 4, 10, 40 }; 
        int n = arr.length; 
        int x = 10; 
        int result = ob.binarySearch(arr, x); 
        if (result == -1) 
            System.out.println("Element not present"); 
        else
            System.out.println("Element found at "
                               + "index " + result); 
    } 
}

کد تکرار شونده الگوریتم جستجوی دودویی در پایتون

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# Python code to implement iterative Binary  
# Search. 
  
# It returns location of x in given array arr  
# if present, else returns -1 
def binarySearch(arr, l, r, x): 
  
    while l <= r: 
  
        mid = l + (r - l)/2; 
          
        # Check if x is present at mid 
        if arr[mid] == x: 
            return mid 
  
        # If x is greater, ignore left half 
        elif arr[mid] < x: 
            l = mid + 1
  
        # If x is smaller, ignore right half 
        else: 
            r = mid - 1
      
    # If we reach here, then the element 
    # was not present 
    return -1
  
  
# Test array 
arr = [ 2, 3, 4, 10, 40 ] 
x = 10
  
# Function call 
result = binarySearch(arr, 0, len(arr)-1, x) 
  
if result != -1: 
    print "Element is present at index % d" % result 
else: 
    print "Element is not present in array"

کد تکرار شونده الگوریتم جستجوی دودویی در #C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// C# implementation of iterative Binary Search 
using System; 
  
class GFG { 
    // Returns index of x if it is present in arr[], 
    // else return -1 
    static int binarySearch(int[] arr, int x) 
    { 
        int l = 0, r = arr.Length - 1; 
        while (l <= r) { 
            int m = l + (r - l) / 2; 
  
            // Check if x is present at mid 
            if (arr[m] == x) 
                return m; 
  
            // If x greater, ignore left half 
            if (arr[m] < x) 
                l = m + 1; 
  
            // If x is smaller, ignore right half 
            else
                r = m - 1; 
        } 
  
        // if we reach here, then element was 
        // not present 
        return -1; 
    } 
  
    // Driver method to test above 
    public static void Main() 
    { 
        int[] arr = { 2, 3, 4, 10, 40 }; 
        int n = arr.Length; 
        int x = 10; 
        int result = binarySearch(arr, x); 
        if (result == -1) 
            Console.WriteLine("Element not present"); 
        else
            Console.WriteLine("Element found at "
                              + "index " + result); 
    } 
} 
// This code is contributed by Sam007

کد تکرار شونده الگوریتم جستجوی دودویی در PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
<?php 
// PHP program to implement 
// iterative Binary Search 
  
// A iterative binary search  
// function. It returns location  
// of x in given array arr[l..r]  
// if present, otherwise -1 
function binarySearch($arr, $l,  
                      $r, $x) 
{ 
    while ($l <= $r) 
    { 
        $m = $l + ($r - $l) / 2; 
  
        // Check if x is present at mid 
        if ($arr[$m] == $x) 
            return floor($m); 
  
        // If x greater, ignore 
        // left half 
        if ($arr[$m] < $x) 
            $l = $m + 1; 
  
        // If x is smaller,  
        // ignore right half 
        else
            $r = $m - 1; 
    } 
  
    // if we reach here, then  
    // element was not present 
    return -1; 
} 
  
// Driver Code 
$arr = array(2, 3, 4, 10, 40); 
$n = count($arr); 
$x = 10; 
$result = binarySearch($arr, 0,  
                       $n - 1, $x); 
if(($result == -1)) 
echo "Element is not present in array"; 
else
echo "Element is present at index ",  
                            $result; 
  
// This code is contributed by anuj_67. 
?> 

خروجی

Element is present at index 3

پیچیدگی زمانی

پیچیدگی زمانی جستجوی دودویی را می‌توان به صورت زیر نوشت:

T(n) = T(n/2) + c

رابطه بازگشتی بالا را می‌توان با استفاده از روش «درخت بازگشتی» (Recursive tree) یا «قضیه اصلی واکاوی (تحلیل) الگوریتم‌ها» (Master method) حل کرد. این رابطه، در حالت دوم قضیه اصلی تحلیل الگوریتم‌ها صدق می‌کند و راهکار بازگشتی به صورت (Theta(Logn است.

«فضای کمکی» (Auxiliary Space)، اگر پیاده‌سازی به صورت تکرار شونده باشد برابر با (O(1 و در صورتی که بازگشتی باشد، از مرتبه (O(Logn فضای پشته فراخوانی بازگشتی است.

منبع: فرادرس

مشاوره جمعه 14 تیر 1398 ساعت 18:12

0 نظر

140
1
...
21
22
صفحه 23
24
25
...
28

طراحی سایت و برنامه نویسی

ابر برجسب

جدیدترین یادداشت‌ها

بایگانی

جستجو

قالب‌های گیت هاب برای درخواست‌های Pull یکپارچه و هوشمندانه — راهنمای کاربردی

مشکلات رایج

درج پیام‌های کامیت خیلی کوتاه

درخواست‌های Pull کاملاً معماگونه

راه‌حل‌ها

گزینه 1: فرایند کاملاً دستی

گزینه 2: قالبی که باید کپی شده و هر بار در PR چسبانده شود

گزینه 3: قالب‌های گیت‌ هاب؛ روش خودکار برای انجام درخواست Pull

راه‌اندازی قالب‌های گیت‌ هاب در یک پروژه

سخن پایانی

یادگیری ماشین در اندروید با ML Kit برای فایربیس — از صفر تا صد

مقدمه

ML Kit برای فایربیس چیست؟

چه چیزی خواهیم ساخت؟

ایجاد یک پروژه روی فایربیس

افزودن اپلیکیشن

پیکربندی AndroidManifest.xml

افزودن یک دوربین به اپلیکیشن

پیکربندی دوربین

عکس گرفتن

شروع تشخیص

ایجاد کادر پیرامونی

سخن پایانی

آموزش Node.js: کار با فایل توسط ماژول fs — بخش نهم

برنامه بررسی وجود دور در گراف بدون جهت — راهنمای کاربردی

برنامه بررسی وجود دور در گراف بدون جهت در ++C

برنامه بررسی وجود دور در گراف بدون جهت در جاوا

برنامه بررسی وجود دور در گراف بدون جهت در پایتون

خروجی

پیچیدگی زمانی

جستجوی دودویی — به زبان ساده

جستجوی دودویی

مثالی از جستجوی دودویی

کد بازگشتی الگوریتم جستجوی دودویی در C

کد بازگشتی الگوریتم جستجوی دودویی در ++C

کد بازگشتی الگوریتم جستجوی دودویی در جاوا

کد بازگشتی الگوریتم جستجوی دودویی در پایتون

کد بازگشتی الگوریتم جستجوی دودویی در #C

کد بازگشتی الگوریتم جستجوی دودویی در PHP

خروجی

کد تکرار شونده الگوریتم جستجوی دودویی در C

کد تکرار شونده الگوریتم جستجوی دودویی در ++C

کد تکرار شونده الگوریتم جستجوی دودویی در جاوا

کد تکرار شونده الگوریتم جستجوی دودویی در پایتون

کد تکرار شونده الگوریتم جستجوی دودویی در #C

کد تکرار شونده الگوریتم جستجوی دودویی در PHP

خروجی

پیچیدگی زمانی