نمایش نتایج 1 تا 15 از 15

نام تاپیک: الگوریتم به دست آوردن زیر مجموعه های یک مجموعه

  1. #1
    منتظر تایید آدرس ایمیل
    تاریخ عضویت
    اردیبهشت 1387
    پست
    2

    Question الگوریتم به دست آوردن زیر مجموعه های یک مجموعه

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

    دنبال یه الگوریتمم که تمام زیر مجموعه های mعضوی از یک مجموعه ی nعضوی رو چاپ کنه
    n,m رو کاربر میده و m<n
    مجموعه nعبارت است از:{1,2,3,4,5,6…n}
    تکرار در زیر مجموعه ها مجاز نیست.یعنی:{1,2,3},{2,1,3}یکی هستند.

    ممنون میشم اگه راهنماییم بکنید.
    راستی اگه خواستید سورس بفرستید به زبان C++‎باشه.

  2. #2
    مدیر بخش آواتار whitehat
    تاریخ عضویت
    مهر 1382
    محل زندگی
    شیراز
    پست
    2,175
    اين كار زياد پيچيده نيست ، بد نيست نگاهي به پياده سازي تركيب (Combination) بياندازيد. تعداد مجموعه هاي m عضوي از يك مجموعه n عضوي برابر تركيب m از n
    پ.ن:اينجا بخش الگوريتم ها است و قرار نيست سورس كدي نوشته شود ، سوالات در مورد زبان مورد نظر را در بخش مربوطه بپرسيد
    To follow the path:
    Look to the master
    Follow the master
    Walk with the master
    See through the master
    Become the master

  3. #3
    منتظر تایید آدرس ایمیل
    تاریخ عضویت
    اردیبهشت 1387
    پست
    2
    آقا ممنون.میشه یکم بیشتر توضیح بدید؟

  4. #4
    با سلام
    فکر می کنم که جوابتون در این فایل باشه.
    فایل های ضمیمه فایل های ضمیمه

  5. #5

    Wink too simple

    سلام

    راستش الان کد رو ندارم. اما روش خیلی ساده است. از یک الگوی بیتی استفاده میشه. اگر مجموعه شما رو 3 عضوی فرض کنیم، کل زیر مجموعه ها 8 تا میشه که این تعداد اعداد باینری قابل تولید بوسیله 3 بیت هم هست. پس شما برای تولید کل زیر مجموعه ها کافیه که اعداد از 0 تا دو به توان n منهای یک رو بشمارید و در هر مرحله معادل باینری عدد رو تولید کنید و چاپ کنید. هر رقم صفر در این اعداد باینری نماینده عدم حضور عضو در زیر مجموعه و هر رقم 1 نماینده حضور اون عضو در زیر مجموعه فعلی است. مثلا اگر مجموعه شامل A,B,C باشه:

    000= زیرمجموعه تهی

    001=C
    --------
    A=100
    --------
    ABC=111
    --------
    AC=101

    , الی آخر...
    اگر نتونستید کدش رو بنویسید بهم بگید...

    پیروز باشید

  6. #6

    نقل قول: الگوریتم به دست آوردن زیر مجموعه های یک مجموعه

    سلام این برنامه یک روش نسبتا ساده داره که می تونید در سایتhttp://ispc.schoolnet.ir/question-01.html توضیحاتی در موردش پیدا کنید برنامه رو هم میذارم اینجا.



    #include<iostream>
    using namespace std;
    int n,k,a[20],tedad;
    void print(){
    for(int i=n-1;i>=0;i--){
    if(a[i]==1){
    cout<<n-i<<" ";
    }
    }
    cout<<endl;
    }
    int main(){
    while(true){
    cin>>n>>k;
    if(n==0 && k==0){
    break;
    }
    cout<<"n="<<n<<",k="<<k<<endl;
    tedad=n;
    for(int i=0;i<n;i++){
    a[i]=1;
    }
    int l;
    while(tedad>0){
    if(tedad==k){
    print();
    }
    l=0;
    while(a[l]==0){
    tedad++;
    a[l]=1;
    l++;
    }
    a[l]=0;
    tedad--;
    }
    }
    return 0;
    }

  7. #7
    کاربر تازه وارد
    تاریخ عضویت
    فروردین 1388
    محل زندگی
    تهران
    سن
    34
    پست
    32

    نقل قول: الگوریتم به دست آوردن زیر مجموعه های یک مجموعه

    میشه تمام زیرمجموعه های مجموعه رو نوشت و زیر مجموعه های m تایی رو نوشت، ولی این روش زمان اجرای خیلی بدی داره. به نظر من این راه بازگشتی بهتره: عضو n رو در نظر بگیر، زیر مجموعه ها رو به دو دسته افراز میکنیم: دسته اول زیرمجموعه هایی که شامل n هستند که میشوند تمام زیر مجوعه های m-1 عضوی مجموعه یک تا n-1 که به اونها n اضافه شده، دسته دوم زیرمجموعه هایی که شامل n نیستند که میشوند زیرمجموعه های m-1 عضوی مجموعه یک تا n-1. حالا این راه بازگشتی رو میشه به صورت پویا هم نوشت.

  8. #8

    نقل قول: الگوریتم به دست آوردن زیر مجموعه های یک مجموعه

    نقل قول نوشته شده توسط newamir مشاهده تاپیک
    میشه تمام زیرمجموعه های مجموعه رو نوشت و زیر مجموعه های m تایی رو نوشت، ولی این روش زمان اجرای خیلی بدی داره. به نظر من این راه بازگشتی بهتره: عضو n رو در نظر بگیر، زیر مجموعه ها رو به دو دسته افراز میکنیم: دسته اول زیرمجموعه هایی که شامل n هستند که میشوند تمام زیر مجوعه های m-1 عضوی مجموعه یک تا n-1 که به اونها n اضافه شده، دسته دوم زیرمجموعه هایی که شامل n نیستند که میشوند زیرمجموعه های m-1 عضوی مجموعه یک تا n-1. حالا این راه بازگشتی رو میشه به صورت پویا هم نوشت.


    سلام میشه بیشتر در مورد تابع بازگشتی واسه این الگوریتم (برای همه زیر مجموعه های یه مجموعه به زبان C) توضیح بدین؟؟؟ممنون

  9. #9

    نقل قول: الگوریتم به دست آوردن زیر مجموعه های یک مجموعه

    دوستان کسی در مورد نوشتن همه ی زیر مجموعه های یه مجموعه با استفاده از تابع بازگشتی میتونه توضیحی واسم بده؟؟ممنون

  10. #10

    Smile زیباترین شیوه بدست آوردن زیر مجوعه های یک مجوعه .. الگوریتم و کد در جاوا

    سلام . با کمی تاخیر نسبت به شروع تاپیک....

    دوستمان در خصوص راه حل بازگشتی مساله پرسیده بودند . من کد این حل به همراه توضیحاتش را برای شما میگذارم . خواستید به سایت ما هم سری بزنید .

    نمک 88 (سایت دانشجویان مهندسی نرم افزار کامیپوتر فردوسی مشهد ورودی 88) . آنجا تا دلتان بخواهد در انجمن ها صحبت سر این جور چیزهاست.

    راه حلی که در زیر می آید ، زیباترین شیوه حل تا کنون است .
    الگوریتم آن به این صورت است :
    R <- []
    L <- [ e1, e2 ... en ]
    c <- 0
    function: powerSet(L, c)
    R <- R union L
    for e in L starting at c
    powerSet(L\{e}, c)
    end
    return R
    end

    پیاده سازی این الگوریتم در جاوا به صورت زیر است:
    publicstaticvoid powerSet(List<String> list, int count)
    {
    result.add(list);
    for(int i = count; i < list.size(); i++)
    {
    List<String> temp = new ArrayList<String>(list);
    temp.remove(i);
    powerSet(temp, i);
    } }
    توضیح الگوریتم : اگر ما بتوانیم مجموعه را به دو زیر مجموعه ای که در یکی یک عضو خاص آمده باشد و در دیگری نیامده باشد ، افراز کنیم ، توانسته ایم یک گام بزرگ در حل بازگشتی مساله برداریم . در این الگوریتم ابتدا لیست شامل اعضا مجموعه گرفته میشود . سپس powerSetدر هر مرحله یک عضو خاص را از مجموعه حذف میکند و تمام زیر مجموعه های بدون عضو خاص را به result اضافه میکند.
    مشخص شدن عضوی که در هر مرحله باید حذف شود ، توسط اندیس ارسال شده به powerSet انجام میشود و عمل حذف در کد جاوا در خط temp.remove(i)صورت میگیرد. سپس دوباره تابع فراخوانی میشود . برای فهم بهتر یک بار تابع را با A={a,b,c} دنبال کنید.
    اشکال این الگوریتم تنها مرتبه زمانی بالای آن (2^n) است.

  11. #11

    نقل قول: الگوریتم به دست آوردن زیر مجموعه های یک مجموعه

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

    افراز با زیر مجموعه فرق داره ها ...

    تعریف و مثال افراز از وکی پدیا ... http://fa.wikipedia.org/wiki/%D8%A7%...88%D8%B9%D9%87

  12. #12

    نقل قول: الگوریتم به دست آوردن زیر مجموعه های یک مجموعه

    به وبلاگ زیر هم یه سری بزنین. شاید به دردتون بخوره:
    http://decoding.blogfa.com/

  13. #13

    نقل قول: الگوریتم به دست آوردن زیر مجموعه های یک مجموعه

    درود دوستان
    من تازه وارد برناه نویسی شدم. یک تمرینی دارم که موفق به نوشتن حلقه هاش نمیشم و شبیه سوال همین تاپیکه با یک تفاوت . میخوام برنامه مثلا 4 تا رقم ( عدد تک رقمی حتی صفر ) را از کاربر بگیره و تمام حالتهایی که این 4 تا رقم میتونند کنار هم قرار بگیرند را در مونیتور نشون بده مثلا 0369 0396 0693 0639 و ...
    فقط حلقه هاشو راهنمایی کنید کافیه . مرسی و بدرودی

  14. #14

    نقل قول: الگوریتم به دست آوردن زیر مجموعه های یک مجموعه

    اگر چهار رقم متمایزباشد ، شما به الگوریتم جایگشت (Permutation) نیاز دارید :
    http://neohoosh.tk/post/142
    http://open-mind.ir/?p=857
    https://barnamenevis.org/showthread.p...A-%D9%87%D8%A7
    http://www.parsiland.com/21125-%D8%A...%B4%DB%8C.html

  15. #15

    نقل قول: الگوریتم به دست آوردن زیر مجموعه های یک مجموعه

    یک برنامه جمع و جور کنسولی برای جایگشت . توجه کنید که برای ورودی از شما یک استرینگ درخواست میشود مثل ABC .
    در خروجی جایگشتهای آن ، یعنی ABC، ACB، BAC و ... درج میشود . میدانیم که تعداد جایگشتهای n شی متمایز برابر n فاکتوریل است .

    //-------------------------------------------------//
    //---- نوشته شده توسط محمد جواد پيشوايي ----- //
    //---- Microsoft Visual Studio 2010 ----- //
    //---- ConsoleApplication ----- //
    //------- جایگشتهای n عنصر --------------------//
    //-------------------------------------------------//
    using System;
    using System.Linq;
    using System.Collections;
    using System.Text;
    using System.IO;
    using System.Collections.Generic;
    using System.Data;
    using System.Diagnostics;


    namespace ConsoleApplication
    {
    class Program
    {
    static int n;
    static char[] mArr;
    static void Main(string[] args)
    {
    string str;
    Console.Write("we obtain permutation of n character In a string . please input string (Ex:ABC) =>");
    str = Console.ReadLine();
    mArr=str.ToCharArray();
    n=mArr.Length-1 ;
    perm(0 );
    Console.ReadKey();
    }
    //-----------------------------------------------------------------------------------------------------------------------
    static void perm(int k)
    {
    if (k == n)
    Console.WriteLine ( String.Concat(mArr));
    else
    {
    for (int i = k; i <= n; i++)
    {
    char temp = mArr[i];
    mArr [i] = mArr[k];
    mArr[k] = temp;
    perm(k + 1);
    mArr[k] = mArr[i];
    mArr[i] = temp;
    }
    }
    }
    //-----------------------------------------------------------------------------------------------------------------------
    }
    }



برچسب های این تاپیک

قوانین ایجاد تاپیک در تالار

  • شما نمی توانید تاپیک جدید ایجاد کنید
  • شما نمی توانید به تاپیک ها پاسخ دهید
  • شما نمی توانید ضمیمه ارسال کنید
  • شما نمی توانید پاسخ هایتان را ویرایش کنید
  •