搜 索

西工大noj数据结构个人答案

  • 1.5k阅读
  • 2021年05月19日
  • 0评论
首页 / Tasks_in_NPU / 正文

第一组

1顺序表的插入运算

noj001.png

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXSIZE 10000
using namespace std;

typedef int Elemtype;
typedef struct
{
    Elemtype elem[MAXSIZE];
    int last; //下标,从0开始;
}Seqlist;

void Init(Seqlist *p) //初始化
{
    int i;
    for(i=0;i<=p->last;i++)
    {
        scanf("%d",&p->elem[i]);
    }
}

int InsList(Seqlist *L,int i,Elemtype e) //插入
{
    int k;
    if((i<1)||(i>L->last+2))
    {
        printf("插入位置不合法");
        return 0;
    }
    if(L->last==MAXSIZE-1)
    {
        printf("表已满,无法插入");
        return 0;
    }
    for(k=L->last;k>=i-1;k--)
        L->elem[k+1]=L->elem[k];
        L->elem[i-1]=e;
        L->last++;
    return 1;
}




int main()
{
    Seqlist *p=(Seqlist*)malloc(sizeof(Seqlist));
    int i,e,k;
    scanf("%d",&p->last);
    p->last--;
    Init(p);
    scanf("%d",&e);

    for(i=0;i<p->last+1;i++)
    {
        if(p->elem[i]>=e) {k=i;break;}
    }
    k++;
    InsList(p,k,e);
    for(i=0;i<=p->last;i++)
    cout<<p->elem[i]<<" ";
    return 0;
}

2线性表的就地逆置

noj002.png

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXSIZE 10000
using namespace std;

typedef int Elemtype;
typedef struct
{
    Elemtype elem[MAXSIZE];
    int last; //下标,从0开始;
}Seqlist;

void Init(Seqlist *p) //初始化
{
    int i;
    for(i=0;i<=p->last;i++)
    {
        scanf("%d",&p->elem[i]);
    }
}

int InsList(Seqlist *L,int i,Elemtype e) //插入,这里i是第几个 和下标不同
{
    int k;
    if((i<1)||(i>L->last+2))
    {
        printf("插入位置不合法");
        return 0;
    }
    if(L->last==MAXSIZE-1)
    {
        printf("表已满,无法插入");
        return 0;
    }
    for(k=L->last;k>=i-1;k--)
        L->elem[k+1]=L->elem[k];
        L->elem[i-1]=e;
        L->last++;
    return 1;
}




int main()
{
    Seqlist *p=(Seqlist*)malloc(sizeof(Seqlist));
    scanf("%d",&p->last);
    p->last--;
    Init(p);
    for(int i=p->last;i>=0;i--)
        cout<<p->elem[i]<<" ";
    cout<<endl;
    for(int i=p->last;i>=0;i--)
        cout<<p->elem[i]<<" ";
    return 0;
}

3顺序表的删除

noj003.png

#include <iostream>

using namespace std;

int a[101];
int b[101];
int c[101];

int main()
{
    //输入
    int m,n,p;
    cin>>m>>n>>p;
    for(int i=0; i<m; i++)
        cin>>a[i];
    for(int i=0; i<n; i++)
        cin>>b[i];
    for(int i=0; i<p; i++)
        cin>>c[i];

    //删除,ijk分别为数组abc的下标,从后往前遍历
    for(int i=m-1,j=n-1,k=p-1; !(i<0 || j<0 || k<0); ) {
        if(b[j]>c[k])         j--;    //如果b的元素较大,b的下标减一
        else if(b[j]<c[k])     k--;
        //此时b[j]==c[k],即找到了相同元素
        else {
            //在a中找这个元素
            while(i>=0 && a[i]>b[j]) i--;
            //如果找到了
            if(i>=0 && a[i]==b[j]) {
                //用覆盖的方式删除
                for(int l=i; l<m-1; l++)
                    a[l]=a[l+1];
                m=m-1;    //a中元素个数减一
                i=i-1;    //a的下标减一
            }
            //如果没找到,b和c的下标需要减一
            if(i>=0 && a[i]!=b[j]) {
                j--;
                k--;
            }
        }
    }

    //输出
    for(int i=0; i<m-1; i++)
        cout<<a[i]<<' ';
    cout<<a[m]<<endl;
    return 0;
}

第二组

4单链表的归并

noj004.png

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
using namespace std;

typedef struct Node
{
    int data;
    struct Node* next;
}LinkNode, * Linklist;

Linklist Initlist() //单链表初始化
{
    Linklist L;
    L = (Linklist)malloc(sizeof(LinkNode));
    L->next = NULL;
    return L;
}

void CreatTail(Linklist L, int n)//尾插法创建单链表
{
    /*int data,i=0;
    Linklist s, tail;
    tail = L;
    cin >> data;
    while (i<n)
    {
        s = (Linklist)malloc(sizeof(LinkNode));
        s->data = data;
        tail->next = s;
        tail = s;
        cin >> data;
        i++;
    }
    tail->next = NULL;*/
    Linklist p;
    p = (Linklist)malloc(sizeof(LinkNode));
    p = L;
    for (int i = 0; i < n; i++)
    {
        p->next = (Linklist)malloc(sizeof(LinkNode));
        cin >> p->next->data;
        p = p->next;
    }
    p->next = NULL;
}

void PrintList(Linklist L) //输出单链表
{
    Linklist p = L->next;
    while (p)
    {
        printf("%d ",p->data);
        p = p->next;
    }
}

/*Linklist merge(Linklist LA, Linklist LB) //有序链表的合并
{
    Linklist pa, pb;
    Linklist LC, r;
    pa = LA->next;
    pb = LB->next;
    LC = LA;
    LC->next != NULL;
    r = LC;
    while (pa && pb)
    {
        if (pa->data >= pb->data)
        {
            r->next = pa; r = pa; pa = pa->next;
        }
        else { r->next = pb; r = pb; pb = pb->next; }
    }
    if (pa) r->next = pa;
    else r->next = pb;
    free(LB);
    return LC;
}*/
Linklist merge(Node *head_a, Node *head_b){
    Node *p,*q,*temp,*head_new;
    p = head_a->next;
    q = head_b->next;
    head_new = head_a;
    head_new->next = NULL;
    //因为需要逆序输出,因此我们采用头插法
    while(p&&q){//当AB链表均非空
        if(p->data<=q->data){//若A节点值较小
            temp = p;
            p = p->next;
            temp->next = head_new->next;
            head_new->next = temp;
        }
        else{//若A节点值较大
            temp = q;
            q = q->next;
            temp->next = head_new->next;
            head_new->next = temp;
        }
    }
    //接下来一定会剩余一条有序空链表,亦或是两条链表全空
    while(p){
        temp = p;
        p = p->next;
        temp->next = head_new->next;
        head_new->next = temp;
    }
    while(q){
        temp = q;
        q = q->next;
        temp->next = head_new->next;
        head_new->next = temp;
    }
    free(head_b);//释放B链表头节点
    return head_new;
}

int main()
{
    int m, n;
    Linklist head_a, head_b;
    head_a = (Linklist)malloc(sizeof(LinkNode));
    head_b = (Linklist)malloc(sizeof(LinkNode));
    cin >> m >> n;
    CreatTail(head_a, m);
    CreatTail(head_b, n);
    PrintList(merge(head_a, head_b));
    return 0;
}

5单链表的删除

noj005.png

/*
8 5 6
1 2 3 4 5 6 6 7
2 3 5 9 12
2 4 5 6 12 13
*/

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
using namespace std;

typedef struct Node
{
    int data;
    struct Node* next;
}LinkNode, * Linklist;

Linklist Initlist(Linklist L); //单链表初始化
void CreatTail(Linklist L, int n);//尾插法创建单链表
void PrintList(Linklist L);//输出单链表
Linklist merge(Node* head_a, Node* head_b);
void deletea(Linklist La, Linklist Lb, Linklist Lc);

int main()
{
    int m, n, p;
    cin >> m >> n >> p;
    Linklist La, Lb, Lc;
    La = (Linklist)malloc(sizeof(LinkNode));
    Lb = (Linklist)malloc(sizeof(LinkNode));
    Lc = (Linklist)malloc(sizeof(LinkNode));
    CreatTail(La, m);
    CreatTail(Lb, n);
    CreatTail(Lc, p);
    deletea(La, Lb, Lc);
    PrintList(La);
    return 0;
}

Linklist Initlist(Linklist L) //单链表初始化
{
    L = (Linklist)malloc(sizeof(LinkNode));
    L->next = NULL;
    return L;
}

void CreatTail(Linklist L, int n)//尾插法创建单链表
{
    Linklist p;
    p = (Linklist)malloc(sizeof(LinkNode));
    p = L;
    for (int i = 0; i < n; i++)
    {
        p->next = (Linklist)malloc(sizeof(LinkNode));
        cin >> p->next->data;
        p = p->next;
    }
    p->next = NULL;
}

void PrintList(Linklist L) //输出单链表
{
    Linklist p = L->next;
    while (p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
}

Linklist merge(Node* head_a, Node* head_b)
{
    Node* p, * q, * temp, * head_new;
    p = head_a->next;
    q = head_b->next;
    head_new = head_a;
    head_new->next = NULL;
    //因为需要逆序输出,因此我们采用头插法
    while (p && q) {//当AB链表均非空
        if (p->data <= q->data) {//若A节点值较小
            temp = p;
            p = p->next;
            temp->next = head_new->next;
            head_new->next = temp;
        }
        else {//若A节点值较大
            temp = q;
            q = q->next;
            temp->next = head_new->next;
            head_new->next = temp;
        }
    }
    //接下来一定会剩余一条有序空链表,亦或是两条链表全空
    while (p) {
        temp = p;
        p = p->next;
        temp->next = head_new->next;
        head_new->next = temp;
    }
    while (q) {
        temp = q;
        q = q->next;
        temp->next = head_new->next;
        head_new->next = temp;
    }
    free(head_b);//释放B链表头节点
    return head_new;
}

void deletea(Linklist La, Linklist Lb, Linklist Lc)
{
    Linklist a = La, b = Lb->next, c = Lc->next;
    Linklist p = a->next;
    while (b && c && a->next)
    {
        if (b->data > c->data) c = c->next;
        else if (b->data < c->data) b = b->next;
        else if(b->data==c->data)
        {
            int tmp = b->data;
            while (p->data < tmp && p->next)//找到相等或者大于的点
            {
                p = p->next;
                a = a->next;
            }
            while (p->data == tmp && p->next) //判断是否相等,若是则删除节点
            {
                p = p->next;
                a->next = p;
            }
            b = b->next;
            c = c->next;
        }

    }

}

6LOCATE操作

noj006.png

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    char data;
    struct node *pre;
    struct node *next;
    int freq;
}Node;

void CreatList(Node *head, int m) {//双链表的创建
    Node *p,*q;
    p = (Node*)malloc(sizeof(Node));
    p = head;
    getchar();
    for(int i=0;i<m;i++){//利用节点q实现双向链表的生成
        q = (Node*)malloc(sizeof(Node));
        scanf("%c",&q->data);
        getchar();
        q->freq = 0;
        p->next = q;
        q->pre = p;
        p = q;
    }
    p->next = NULL;
}

void Locate(Node *head,int n){
    char c;
    for(int i=0;i<n;i++){
        Node *p = head->next;
        scanf("%c",&c);
        getchar();
        while(p!=NULL){//遍历链表进行权数freq的自增
            if(p->data == c){
                p->freq++;
            }
            p = p->next;
        }
    }
}

void BubbleSort(Node *head,int m){ //这是比较简单的交换数据完成的冒泡排序,但没有使用双链表的双向性质,破坏了双链表pre指针
    Node *p = head->next;
    while (m > 1) {
        while (p->next != NULL) {
            if (p->freq < p->next->freq) {
                char c;
                int f;
                c = p->data;
                f = p->freq;
                p->data = p->next->data;
                p->freq = p->next->freq;
                p->next->data = c;
                p->next->freq = f;
            }
            p = p->next;
        }
        m--;
        p = head->next;
    }
}

void Sort(Node *head,int m){  //这是用双链表的指针交换排序的,这个函数有一些问题,不能正常运行,仅提供思路,所以本题没有使用本函数
    Node *p = head->next;
    Node *q;
    for(int i=1;i<m;i++){
        p = head->next;
        for(int j=1;j<=m-i&&p->next;j++){
            if(p->freq < p->next->freq){
                if(p->next->next==NULL){
                    q = p->next;
                    p->pre->next = q;
                    q->pre = p->pre;
                    p->pre = q;
                    p->next = NULL;
                    q->next = p;
                }
                q = p->next;
                p->pre->next = q;
                q->pre = p->pre;
                p->pre = q;
                p->next = q->next;
                q->next->pre = p;
                q->next = p;
            }
            p = p->next;
        }
    }
}

void PrintList(Node *head){//输出链表
    Node *p = head->next;
    while(p){
        printf("%c ",p->data);
        p = p->next;
    }
}

int main(){
    Node *head;
    head = (Node*)malloc(sizeof(Node));
    int m,n;
    scanf("%d %d",&m,&n);
    CreatList(head,m);
    Locate(head,n);
    BubbleSort(head,m);
    PrintList(head);
    return 0;
}

第三组

7表达式括号匹配

noj007.png

//[5+(6-3)]-(2+3)]

#include<stdio.h>  
#include<string.h>  
#include<stdlib.h>  
  
typedef struct Stack{  
    char data;  
    struct Stack *next;  
}Stack;  
  
Stack *create(){  
    Stack *q=(Stack *)malloc(sizeof(Stack));  
    q->next=NULL;  
    return q;  
}  
  
char getTop(Stack *s){  
    return s->next->data;  
}  
  
int equals(char a,char b){  
    if(a=='('&&b==')')return 1;  
    if(a=='['&&b==']')return 1;  
    if(a=='{'&&b=='}')return 1;  
    return 0;  
}  
  
void pop(Stack *s){  
    Stack *q=s->next;  
    s->next=q->next;  
    free(q);  
}  
  
void push(Stack *s,char b){  
    Stack *q=(Stack *)malloc(sizeof(Stack));  
    q->data=b;  
    q->next=s->next;  
    s->next=q;  
}  
int isEmpty(Stack *s){  
    if(s->next==NULL)return 1;  
    return 0;  
}  
  
int main(){  
    char str[105];  
    scanf("%s",str);  
    int i=0;  
    int len=strlen(str);  
    Stack *s=create();  
    if(str[0]=='['||str[0]==']'||str[0]=='{'||str[0]=='}'||str[0]=='('||str[0]==')')  
        push(s,str[0]);  
    for(i=1;i<len;i++){  
        if(!isEmpty(s)&&equals(getTop(s),str[i]))  
        {  
            pop(s);  
        }  
        else  
        {  
            if(str[i]=='['||str[i]==']'||str[i]=='{'||str[i]=='}'||str[i]=='('||str[i]==')')  
                push(s,str[i]);  
        }  
    }  
    if(isEmpty(s)){  
        printf("yes\n");  
    }else{  
        printf("no\n");  
    }  
    return 0;  
}  
//my code
//[5+(6-3)]-(2+3)]
#include<stdio.h>  
#include<string.h>  
#include<stdlib.h> 

typedef struct Stack{
    char data;
    struct Stack *next;
}Stack;

Stack *CreateStack()
{
    Stack *p=(Stack*)malloc(sizeof(Stack));
    p->next=NULL;
    return p;
}

char gettop(Stack *s)
{
    return s->next->data;
}

void push(Stack *s,char a)
{
    Stack *p=(Stack*)malloc(sizeof(Stack));
    p->data=a;
    p->next=s->next;
    s->next=p;
}

void pop(Stack *s)
{
    Stack *p;
    p=s->next;
    s->next=s->next->next;
    free(p);
}

int IsEmpty(Stack *s)
{
    if(s->next==NULL) return 1;
    else return 0;
}

int match(char a,char b)
{
    if((a=='('&&b==')')||(a=='['&&b==']')||(a=='{'&&b=='}')) return 1;
    else return 0;
}

int main()
{
    char str[100];
    scanf("%s",str);
    Stack *s=CreateStack();
    for(int i=0;str[i]!='\0';i++)
    {
        switch (str[i])
        {
        case '(':
        case '[':
        case '{':
            push(s,str[i]);
            break;
        case '}':
        case ')':
        case ']':
            if(IsEmpty(s)) {printf("no");return 0;}
            else
            {
                if(match(gettop(s),str[i])) pop(s);
                else {printf("no");return 0;}
            }
            break;
        }
    }
    if(IsEmpty(s)) {printf("yes");}
    else printf("no");
    return 0;
}

8逆波兰式

noj008.png

  • 1.如果是字符,则直接输出

    2.如果是运算符,则就需要比较这个运算符和栈顶元素的优先级别了,假设之前栈顶的运算符为c1,后来读取的运算符为c2。

    则有:

    如果c2优先级高于c1,那么c2压进S1栈储存
    如果c2优先级低于c1,那么S1将c1弹出输出,然后比较新的S1的栈顶元素和c2,如果还是c2优先级别低,那就再弹一个c1,最后直到c1的优先级别低于c2,此时将c2压进栈S1。
    特殊情况:如果c1为(,则直接压入。
    
//(a+b)*c
//my code
#include<stdio.h>  
#include<string.h>  
#include<stdlib.h> 
#include<iostream>

using namespace std;

typedef struct Stack{
    char data;
    struct Stack *next;
}Stack;

Stack *CreateStack()
{
    Stack *p=(Stack*)malloc(sizeof(Stack));
    p->next=NULL;
    return p;
}

char gettop(Stack *s)
{
    if(s->next==NULL) return 0;
    return s->next->data;
}

void push(Stack *s,char a)
{
    Stack *p=(Stack*)malloc(sizeof(Stack));
    p->data=a;
    p->next=s->next;
    s->next=p;
}

char pop(Stack *s)
{
    char x;
    Stack *p;
    if(s->next==NULL) return 0;
    x=s->next->data;
    p=s->next;
    s->next=s->next->next;
    free(p);
    return x;
}

int IsEmpty(Stack *s)
{
    if(s->next==NULL) return 1;
    else return 0;
}

void InfixToPostfix(char *r)
{   
    char x;//存储弹出来的元素
    Stack *s=CreateStack();
    for(;*r!='\0';r++)
    {
        switch(*r)
        {
        case '(': push(s,*r);break;//直接压进去
        case ')': //)不进入,遍历栈元素,将(前元素弹出来输出,(弹出来不输出
            while(gettop(s)!='(')
            {
                x=pop(s);
                cout<<x;//直接弹出来输出
            }
            pop(s);//弹出(
            break;
        case '*':
        case '/'://如果栈为空,或者遇到+ - (则直接压入;如果为* /,则直接pop输出          
            while(s->next==NULL||gettop(s)=='*'||gettop(s)=='/')
            {
                if(s->next==NULL) break;
                x=pop(s);
                cout<<x;
            }
            push(s,*r);//压入*or/ 
            break;
        case '+':
        case '-'://如果为空,或者遇到(则直接压入;如果为+-*/则直接pop输出
            while(s->next==NULL||gettop(s)=='+'||gettop(s)=='-'||gettop(s)=='*'||gettop(s)=='/')
            {
                if(s->next==NULL) break;
                x=pop(s);
                cout<<x;
            }
            push(s,*r);//压入*or/   
            break;
        default:
            cout<<*r;
        }
        
    }
    while(s->next!=NULL)//清空弹出输出栈
    {
        cout<<pop(s);
    }
}

int main()
{
    char str[100];
    scanf("%s",str);
    InfixToPostfix(str);
    return 0;
}

9循环队列

noj009.png

/*
5
3 4 6 2 7
yes
4
*/
//my code
//
#include<stdio.h>  
#include<string.h>  
#include<stdlib.h> 
#include<iostream>

using namespace std;

typedef struct node{
    int *data;
    int front,rear,len;
    int n;//队列长度
}Queue;

Queue *CreateQueue(int k)//输入队列长度,返回队列
{
    Queue *p=(Queue*)malloc(sizeof(Queue));
    p->data=(int*)malloc(sizeof(int)*k);//数组大小
    p->front=p->rear=p->len=0; //归零
    p->n=k;//n为队列长度
    return p;
}

void push(Queue *q,int i)
{
    q->data[q->rear] = i;
    q->rear=(q->rear+1)%(q->n);
    q->len++;
}

int pop(Queue *q)
{
    q->front=(q->front+1)%q->n;
    q->len--;
    return q->data[q->front-1];
}

int gettop(Queue *q)
{
    return q->data[q->front];
}

void output(Queue q)
{
    for(int i=q.front;i<q.front+q.len;i++)
    {
        cout<<q.data[i]<<" ";
    }
    cout<<endl;
}

int main()
{
   Queue *p;
   int k;
   int i;
   int x;
   char c;
   cin>>k;
   p=CreateQueue(k);
   while(1)
   {
       cin>>i;
       push(p,i);
       c=getchar();
       if(c=='\n') break;
   }

    string s;
    cin>>s;
    cin>>x;
    while(pop(p)!=x);
8
    output(*p);
    cout<<gettop(p);
    return 0;
}

10.k阶菲波那契数列

noj0010.png

==描述==
已知K阶斐波那契数列定义为:
f0 = 0, f1 = 0, … , fk-2 = 0, fk-1 = 1;
fn = fn-1 + fn-2 + … + fn-k , n = k , k + 1, …
利用循环队列编写求k阶斐波那契数列中前n+1项(f0, f1, f2,…, fn)的算法,要求满足:fn<=max,并且fn+1>max,其中max为某个约定的常数。(注意:本题所用循环队列的容量仅为k,则在算法执行结束时,留在队列中的元素应是所求k阶斐波那契序列中的最后k项fn-k-1 , fn-k, …, fn)。

k阶斐波那契序列定义:第k和k+1项为1,前k - 1项为0,从k项之后每一项都是前k项的和

如:k=2时,斐波那契序列为:0,1,1,2,3,5,...

​ k=3时,斐波那契序列为:0,0,1,1,2,4,7,13,...

==输入==
输入表示阶数的k(2<= k <= 100)以及表示某个常数的max(0 <= max <= 100000)。

==输出==
输出满足条件的项n(n从0开始计数),占一行;
以及第n项的值,占一行;
输出一个回车符。

==输入样例==
4 10000

==输出样例==
17
5536

==化简一下,得到迭代公式:==
①:f(m)=f(m-1)+f(m-2)+…+f(m-k)
②:f(m-1)=f(m-2)+f(m-3)+…+f(m-k-1)
①-②: f(m)-f(m-1)=f(m-1)-f(m-k-1)
f(m)=2f(m-1)-f(m-k-1)

以上是资料,我调了半天这个题,wdm啊,最后是。。举个例子,k=2,我就开4个,留一个空的,然后三个是因为方便那个迭代公式的计算,然后当判断到下一次要push进来的f(m)大于max时候就不push了,按题意我只要这时候把队列rear前面的俩输出就行了。

//my code
//14 2
#include<stdio.h>  
#include<string.h>  
#include<stdlib.h> 
#include<iostream>

using namespace std;

typedef struct node{
    int *data;
    int front,rear;
    int n;//队列长度
}Queue;

Queue *CreateQueue(int k)//输入队列长度,返回队列
{
    k++;
    Queue *p=(Queue*)malloc(sizeof(Queue));
    p->data=(int*)malloc(sizeof(int)*(k+1));//数组大小,空出一个判断是否满队列,这里如果k为2就开辟4个空间方便计算公式
    p->front=p->rear=0; //归零
    p->n=k+1;//n为队列长度+1
    return p;
}

void push(Queue *q,int i)
{
    if((q->rear+1)%q->n==q->front) return;
    else{
    q->data[q->rear] = i;
    q->rear=(q->rear+1)%(q->n);
    }
}

int pop(Queue *q)
{
    q->front=(q->front+1)%q->n;
    return q->data[q->front-1];
}

int gettop(Queue *q)
{
    return q->data[q->front];
}

void output(Queue q,int k)//输出最后k项
{
    int j=(q.rear-k+q.n)%q.n;
    for(int i=0;i<k;i++)
    {
        cout<<q.data[j]<<" ";
        j=(j+1)%q.n;
    }
    cout<<endl;
}

//fibonacci递归
void Fibonacci(Queue *q,int max,int k)
{
    int i=0,j=0,tmp=0;
    for(i=0;i<=k;i++)
    {
        if(i>=k-1) push(q,1);
        else push(q,0);
    }
    while(tmp<=max)
    {
        tmp=2*q->data[(q->rear-1+q->n)%q->n]-q->data[(q->rear-k-1+q->n)%q->n];//f(m)=2f(m-1)-f(m-k-1) 
        if(tmp<=max) 
        {pop(q);
        push(q,tmp);}
        else break;
    }
}

int main()
{
    int max,k;
    cin>>max>>k;
    Queue *q=CreateQueue(k);
    Fibonacci(q,max,k);
    output(*q,k);
    return 0;
}

11.循环右移

noj011.png

终于碰到简单到我会做的题了呜呜呜

//my code
/*
6 3
1 2 3 4 5 6*/
#include<stdio.h>  
#include<string.h>  
#include<stdlib.h> 
#include<iostream>

using namespace std;
int main()
{
    int n,k;
    int *a;
    cin>>n>>k;
    a=(int*)malloc(sizeof(int)*(n+1));
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=k;i++)
    {
        a[0]=a[n];
        for(int j=n;j>=1;j--)
        {
            a[j]=a[j-1];
        }
    }
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
    return 0;
}
无标签
《水星记》
« 上一篇
Trash 0
下一篇 »
评论区
暂无评论
avatar